这道题是再典型不过的DFS了, 当然也可以用Union Find做。
我居然犯了如下错误.
- dfs的ans忘了初始化为1了, 我说为什么一直结果是0来着,
2。 nr >= N || nc >= N 这儿写错了。
class Solution {
int[][] OFFSETS;
public int maxAreaOfIsland(int[][] grid) {
int N = grid.length, M = grid[0].length;
OFFSETS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
boolean[][] visited = new boolean[N][M];
int ans = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < M; c++) {
ans = Math.max(ans, dfs(grid, visited, r, c, N, M));
}
}
return ans;
}
private int dfs(int[][] grid, boolean[][] visited, int r, int c, int N, int M) {
if (visited[r][c] || grid[r][c] == 0) return 0;
visited[r][c] = true;
int ans = 1; //差点忘了设为1了 。。。
for (int[] os : OFFSETS) {
int nr = os[0] + r, nc = os[1] + c;
if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
ans += dfs(grid, visited, nr, nc, N, M);
}
return ans;
}
}