leetcode 695. 岛屿的最大面积

【岛屿专题2】
leetcode 695. 岛屿的最大面积
同 剑指 Offer II 105. 岛屿的最大面积

代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1){
                    int count = dfs(grid,i,j);
                    maxArea = count > maxArea ? count : maxArea;
                }
            }
        }
        return maxArea;
    }
    public int dfs(int[][] grid, int i, int j){
        //如果不在范围内返回0
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) return 0;
        //如果不为1，也返回0（ 0表示海水，2表示陆地已经搜索过）
        if(grid[i][j] != 1) return 0;
        //搜索后对陆地进行标记，防止再次搜索
        grid[i][j] = 2;
        //根据规则(上下左右)进行搜索(
        //解释：经过了前面两个判断，当走到这一步时，说明一定存在一块陆地，所以返回1。后面4个搜索表示从当前这个位置出发搜索与之相连的陆地，如果搜索的是陆地则返回1并继续搜索递归下去，直到返回0终止。
        /**其实这里也可以写成这种形式：
        int a = dfs(grid,i+1,j); //上
        int b = dfs(grid,i-1,j); //下
        int c = dfs(grid,i,j-1); //左
        int d = dfs(grid,i,j+1); //右
        return 1 + a + b + c + d;
        这样比较清晰，但是繁琐，和下面合并在一起写是一样的
        */
        return 1 + dfs(grid,i+1,j) + dfs(grid,i-1,j) + dfs(grid,i,j-1) + dfs(grid,i,j+1);
        //PS:这里可以尝试手动推两层就会比较清晰
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34