【DFS】1254. 统计封闭岛屿的数目

1254. 统计封闭岛屿的数目

解题思路

• 封闭岛屿就是上下左右全部被1包围的0 也就是靠边的0不算做封闭岛屿
• 首先将上下左右的边界上的岛屿全部变成海洋
• 然后在对剩下的岛屿进行DFS遍历

class Solution {
    public int closedIsland(int[][] grid) {
        // 封闭岛屿就是上下左右全部被1包围的0  也就是靠边的0不算做封闭岛屿


        // 计算封闭岛屿的数量

        int m = grid.length;
        int n = grid[0].length;

        for(int i = 0; i < n; i++){
            // 将上下的岛屿 全部变成海洋

            // 第0行的所有列
            dfs(grid,0,i);

            // 最后一行的所有列
            dfs(grid,m - 1,i);
        }

        // 将左右变成海洋
        for(int j = 0; j < m; j++){
            dfs(grid,j,0);
            dfs(grid,j,n - 1);
        }

        // 遍历剩下的岛屿

        int res = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 0){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }


        return res;

    }

    // DFS遍历

    void dfs(int[][] grid,int i,int j){
        int m = grid.length;
        int n = grid[0].length;

        if(i < 0 || j < 0 || i >= m || j >= n){
            return;
        }

        if(grid[i][j] == 1){
            return;// 如果已经遍历到海水
        }

        // 遍历到岛屿 变成1
        if(grid[i][j] == 0){
            grid[i][j] = 1;
        }

        dfs(grid,i + 1,j);
        dfs(grid,i,j + 1);
        dfs(grid,i - 1,j);
        dfs(grid,i,j - 1);
    }
}

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69