題目

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

找到給定的二維數(shù)組中最大的島嶼面積。(如果沒(méi)有島嶼，則返回面積為0。)

示例 1:

[[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]]
對(duì)于上面這個(gè)給定矩陣應(yīng)返回 6。注意答案不應(yīng)該是11，因?yàn)閸u嶼只能包含水平或垂直的四個(gè)方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]]
對(duì)于上面這個(gè)給定的矩陣, 返回 0。
注意: 給定的矩陣grid 的長(zhǎng)度和寬度都不超過(guò) 50。

思路

類似于深度優(yōu)先搜索，使用遞歸的方法。就是深度搜索每一個(gè)值為1的點(diǎn)，然后找到面積最大的一個(gè)，把每一個(gè)已經(jīng)搜索過(guò)的點(diǎn)置零，這樣就能避免重復(fù)搜索以減少計(jì)算量。

代碼

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for(int i = 0;i < grid.length;i++){
            for(int j = 0;j < grid[0].length;j++){
                if(grid[i][j] == 1){
                    int num = deepSearch(grid,i,j);
                    max = Math.max(num,max);
                }
            }
        }
        return max;
    }
    public int deepSearch(int[][] grid,int i,int j){
        if(i>=0&&i<grid.length&&j>=0&&j<grid[0].length&&grid[i][j] == 1){
            grid[i][j]=0;
            int num = 1 + deepSearch(grid,i-1,j) + deepSearch(grid,i+1,j) + deepSearch(grid,i,j-1) + deepSearch(grid,i,j+1);
            return num;
        }else
            return 0;
    }
}