## 题目描述

Given a non-empty 2D array `grid` of 0's and 1's, an island is a group of `1`'s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

``````[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]``````

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

``[[0,0,0,0,0,0,0,0]]``

Given the above grid, return `0`.

Note: The length of each dimension in the given `grid` does not exceed 50.

## 解法一

### 思路

• 为了避免DFS重复计数，对于访问过的`1`，马上置为`0`即可。
• 注意到DFS是一个递归的过程，所以每一层只需要返回本身的计数（1）以及其子递归返回的计数（由此处出发DFS遍历到的`1`的个数）的和就可以了。

### Python

``````class Solution:
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
steps = ((-1, 0), (1, 0), (0, -1), (0, 1))

def dfs(grid, x, y, m, n):
if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == 0:
return 0
count = 1
grid[x][y] = 0
for i, j in steps:
count += dfs(grid, x + i, y + j, m, n)
return count

result = 0
m = len(grid)
n = len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
result = max(result, dfs(grid, i, j, m, n))
return result``````

### Java

``````class Solution {
public int maxAreaOfIsland(int[][] grid) {
class Utils {
int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int dfs(int[][] grid, int x, int y, int m, int n) {
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
return 0;
}
int count = 1;
grid[x][y] = 0;
for (int[] step : steps) {
count += dfs(grid, x + step[0], y + step[1], m, n);
}
return count;
}
}
int result = 0;
int m = grid.length;
int n = grid[0].length;
Utils utils = new Utils();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
result = Math.max(result, utils.dfs(grid, i, j, m, n));
}
}
}
return result;
}
}``````

### C++

``````class Solution {
public:
int maxAreaOfIsland(vector<vector<int>> &grid) {
class Utils {
public:
int steps[4][2] = {{-1, 0},
{1,  0},
{0,  -1},
{0,  1}
};

int dfs(vector<vector<int>> &grid, int x, int y, int m, int n) {
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
return 0;
}
int count = 1;
grid[x][y] = 0;
for (auto &step : steps) {
count += dfs(grid, x + step[0], y + step[1], m, n);
}
return count;
}
};
int result = 0;
int m = grid.size();
int n = grid[0].size();
Utils utils;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
result = max(result, utils.dfs(grid, i, j, m, n));
}
}
}
return result;
}
};``````