島嶼的最大面積

題目描述

給定一個包含了一些 0 和 1的非空二維數(shù)組 grid , 一個 島嶼 是由四個方向 (水平或垂直) 的 1 (代表土地) 構(gòu)成的組合。你可以假設(shè)二維矩陣的四個邊緣都被水包圍著。

找到給定的二維數(shù)組中最大的島嶼面積。(如果沒有島嶼，則返回面積為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]]
對于上面這個給定矩陣應(yīng)返回 6。注意答案不應(yīng)該是11，因為島嶼只能包含水平或垂直的四個方向的‘1’。

提示：
注意: 給定的矩陣grid 的長度和寬度都不超過 50。

轉(zhuǎn)載來源：力扣（LeetCode）

題目分析

這題 我用了一種不知道叫什么方法的方法來解決，姑且叫它普通遍歷法吧，擊敗了雙100的Java用戶。

• 對于一個點grid[i][j]，如果它是海水，自然就不用計算，直接跳過；
• 對于一個點grid[i][j]，如果它是陸地，那么和它相連的陸地總面積 = 它左邊陸地的面積 + 它右邊陸地的面積 + 它上面陸地的面積 + 它下面的陸地的面積 + 1（它自身）；
• 對于上述中的grid[i][j]上下左右陸地的面積，也同樣可以用上面的思路來獲取，顯然可以用遞歸解決；
• 為了防止grid[i][j]左邊陸地grid[i][j - 1]計算陸地面積的時候把grid[i][j]重復(fù)計算進去，在grid[i][j]請求獲取grid[i][j - 1]陸地面積之前把grid[i][j]置為0，因為這一塊的面積是第二步里的+1，這樣置零是最重要的一步，既防止重復(fù)計算，又防止左算右又算左的無限死循環(huán)；
• 我好了，完事了，你呢？

    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;
    }