题目描述
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为0。)
样例
input:
[[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]]
output:6
input:
[[0,0,0,0,0,0,0,0]]
output:0
dfs
$O(nm)$
1.从任意一个陆地点开始,即可通过四连通的方式,深度优先搜索遍历到所有与之相连的陆地,即遍历完整个岛屿;遍历结束后将遍历过的点清0。
2.重复以上过程,记录最大的返回值即可。
时间复杂度分析:由于每个点最多被遍历常数次,故时间复杂度为O(nm)。
Java 代码
class Solution {
private int[] dx = {1,-1,0,0};
private int[] dy = {0,0,1,-1};
int row, col;
public int maxAreaOfIsland(int[][] grid) {
if(grid==null || grid.length==0 || grid[0].length==0)
return 0;
row = grid.length;
col = grid[0].length;
int maxArea =0;
for(int i=0;i<row;i++) {
for(int j = 0;j<col;j++) {
maxArea = Math.max(maxArea, dfs(grid,i,j));
}
}
return maxArea;
}
private int dfs(int[][] grid, int x, int y) {
if(x < 0 || x>=row || y < 0|| y>=col || grid[x][y]==0)
return 0;
int area = 1;
grid[x][y] = 0;
for(int i = 0;i<dx.length;i++)
area += dfs(grid,x+dx[i],y+dy[i]);
return area;
}
}