岛屿的最大面积
题目描述
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
示例：
[[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]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。
提示：
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
题目分析
这题 我用了一种不知道叫什么方法的方法来解决，姑且叫它普通遍历法吧，击败了双100的Java用户。
- 对于一个点grid[i][j]，如果它是海水，自然就不用计算，直接跳过；
- 对于一个点grid[i][j]，如果它是陆地，那么和它相连的陆地总面积 = 它左边陆地的面积 + 它右边陆地的面积 + 它上面陆地的面积 + 它下面的陆地的面积 + 1（它自身）；
- 对于上述中的grid[i][j]上下左右陆地的面积，也同样可以用上面的思路来获取，显然可以用递归解决；
- 为了防止grid[i][j]左边陆地grid[i][j - 1]计算陆地面积的时候把grid[i][j]重复计算进去，在grid[i][j]请求获取grid[i][j - 1]陆地面积之前把grid[i][j]置为0，因为这一块的面积是第二步里的+1，这样置零是最重要的一步，既防止重复计算，又防止左算右又算左的无限死循环；
- 我好了，完事了，你呢？
public int maxArea = 0;
public int[][] grid;
public int maxAreaOfIsland(int[][] grid) {
this.grid = grid;
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
int area = search(i,j);
if(area > maxArea)
maxArea = area;
}
}
return maxArea;
}
public int search(int v,int h){
if(v >= grid.length || v < 0
|| h < 0 || h >= grid[0].length
|| grid[v][h] == 0) return 0;
grid[v][h] = 0;
int up = search(v - 1,h);
int dowm = search(v + 1,h);
int left = search(v,h - 1);
int right = search(v,h + 1);
return 1 + up + dowm + left + right;
}
