695. 岛屿的最大面积

岛屿的最大面积

题目描述

给定一个包含了一些 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。

转载来源：力扣（LeetCode）

题目分析

这题 我用了一种不知道叫什么方法的方法来解决，姑且叫它普通遍历法吧，击败了双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;
    }