This page looks best with JavaScript enabled

岛屿数量

 ·  ☕ 2 min read

给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围

问题

给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围.

输入:
11110
11010
11000
00000

输出: 1
输入:
11000
11000
00100
00011

输出: 3

思考

由题意可知: 如果二维网格中的一系列 1 是连续不间断的, 则说明他们是一个岛屿. 所以可以计数一个 1 节点能到达的所有节点, 能到达的 1 节点都属于同一个岛屿, 在查找路径过程中如果遇到了 0 则代表走到了岛屿边界, 结束该节点的路径查找, 继续找下一个没有被访问过 1 节点作为查找的起点.

综上, 可使用 BFS 思想, 以一个 1 节点为起点, 找到该节点能到达的所有路径, 这些路径便组成了一个岛. 下一次查找则需要从一个没有被访问过的 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class Solution {
    // 从每个节点开始 BFS 遍历, 直到遇到 0 结束. BFS 会遍历完与一个节点相连的所有节点, 同时要保证一个节点只会被访问1次(通过将节点记为 0 表示已经访问过)
    public int numIslands(char[][] grid) {
        if(grid==null || grid.length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        
        // 上下左右邻居与当前节点的索引的差值
        int[][] neiber = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        
        for(int i=0; i< m; i++) {
            for (int j=0; j<grid[i].length; j++) {
                // 遇到 0 节点不用访问
                if(grid[i][j] == '0'){
                    continue;
                }
                
                count ++;
                
                Deque<Integer> que = new ArrayDeque();
                que.add(i*n+j);

                while(!que.isEmpty()) {
                    int cur = que.pop();
                    int row = cur/n;
                    int column = cur%n;

                    // System.out.println("v:" + row+","+ column);
                    
                    // 代替下面注释的添加邻居的代码
                    for(int k=0; k< neiber.length; k++){
                        int r = neiber[k][0] + row;
                        int col = neiber[k][1] + column;
                        if(r > -1 && r < grid.length && col > -1 && col < grid[row].length && grid[r][col] != '0') {
                            que.add(r*n+col);
                            grid[r][col] = '0'; // 标记为已访问, 避免重复添加
                            // System.out.println("enque:" + r + "," + col);
                        }
                    }
                    
                    /*
                    // 添加邻居
                    if(row-1 > -1) {
                        int c = (row-1)*n+column;
                        char item = grid[row-1][column];
                        if(item != '0'){
                            que.add(c);
                            // 避免重复添加
                            grid[row-1][column] = '0';
                            System.out.println("enque:" + (row-1) + "," + column);
                        }
                    }
                    if(column-1 > -1 ){
                        int c = row*n+column-1;
                        char item = grid[row][column-1];
                        if(item != '0'){
                            que.add(c);
                            // 避免重复添加
                            grid[row][column-1] = '0';
                            System.out.println("enque:" + row + "," + (column-1));
                        }
                    }
                    if(row+1 < grid.length) {
                        int c = (row+1)*n+column;
                        char item = grid[row+1][column];
                        if(item != '0'){
                            que.add(c);
                            // 避免重复添加
                            grid[row+1][column] = '0';
                            System.out.println("enque:" + (row+1) + "," + column);
                        }
                    }
                    if(column+1 < grid[row].length) {
                        int c = row*n+column+1;
                        char item = grid[row][column+1];
                        if(item != '0'){
                            que.add(c);
                            // 避免重复添加
                            grid[row][column+1] = '0';
                            System.out.println("enque:" + row + "," + (column+1));
                        }
                    }
                    */
                }
            }
        }

        return count;
    }
}

Yang
WRITTEN BY
Yang
Developer