岛屿数量

200.岛屿数量

题意

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

思路一（DFS）

解决岛屿题目最常见的就是 DFS 了，每次遇到一个岛屿中的陆地，就用 DFS 把这个岛屿「淹掉」。

把二维数组中的每个格子看做「图」中的一个节点，这个节点和周围的四个节点连通，这样二维矩阵就被抽象成了一幅网状的「图」。

为什么每次遇到岛屿，都要用 DFS 把岛屿「淹了」呢？主要是为了省事，避免维护 visited 数组。因为遍历图是需要 visited 数组记录遍历过的节点防止走回头路。

由于 dfs 函数遍历到值为 0 的位置会直接返回，所以只要把经过的位置都设置为 0，就可以起到不走回头路的作用。

最终岛屿的数量就是每次发现新岛屿的次数。

代码：

class Solution {
    void dfs(char[][] g, int i, int j) {
        int n = g.length, m = g[0].length;

        // 先判断范围和条件
        if (i < 0 || i >= n || j < 0 || j >= m) return;
        if (g[i][j] == '0') return;

        // 将遍历过的陆地淹没
        g[i][j] = '0';
        // 遍历上下左右四个方向
        dfs(g, i + 1, j);
        dfs(g, i, j + 1);
        dfs(g, i - 1, j);
        dfs(g, i, j - 1);
    }

    public int numIslands(char[][] g) {
        int res = 0;
        int n = g.length, m = g[0].length;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                // 每发现一个新岛屿，加入进来
                if (g[i][j] == '1'){
                    res++;
                    // 使用dfs将连通的陆地块淹掉
                    dfs(g, i, j);
                }
            }
        }

        return res;
    }
}

思路二（BFS）

广搜需要通过队列实现，每走过一个节点，就要加入队列并标记为「淹没」。

遍历整个二维数组。如果一个位置为 '1'，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 '1' 都会被重新标记为 '0'。直到队列为空，搜索结束。

最终岛屿的数量就是进行广度优先搜索的次数。

class Solution {
    int n, m;
    char[][] g;
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};

    void bfs(int i, int j) {
        Queue<Pair<Integer, Integer>> q = new LinkedList<>();
        
        q.offer(new Pair<>(i, j));
        g[i][j] = '0';
        while (!q.isEmpty()){
            Pair<Integer, Integer> t = q.poll();
            int x = t.getKey();
            int y = t.getValue();
            for (int k = 0; k < 4; k++){
                int xx = x + dx[k], yy = y + dy[k];
                if (xx < 0 || xx >= n || yy < 0 || yy >= m || g[xx][yy] == '0') continue;
                q.offer(new Pair<>(xx, yy));
                g[xx][yy] = '0';
            }
        }
    }

    public int numIslands(char[][] g) {
        n = g.length;
        m = g[0].length;
        this.g = g;
        
        int res = 0;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (g[i][j] == '1'){
                    bfs(i, j);
                    res++;
                }
            }
        }

        return res;
    }
}

思路三（并查集）

遍历整个二维数组。如果一个位置为 '1'，则将其与相邻四个方向上的 '1' 在并查集中进行合并。

因为是从（0,0）往（n，m）按顺序遍历，所以可以优化为每次只搜「右边」和「下边」的位置，因为「左边」和「上边」在之前的搜索中已经加入到集合了，不需要再搜了。

最终岛屿的数量就是并查集中连通分量的数目。

代码：

class Solution {
    int[] p;
    int res;

    int find(int i) {
        return p[i] == i ? p[i] : find(p[i]);
    }

    void union(int i, int j){
        if (find(i) == find(j)) return;  // 避免重复合并操作
        p[find(i)] = p[find(j)];
        res--;
    }

    public int numIslands(char[][] g) {
        int n = g.length, m = g[0].length;
        p = new int[n * m];
        res = 0;
        
        // 初始化 parent 数组，记录初始岛屿数（也就是 '1' 的数目）
        for (int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                int idx = i * m + j;
                p[idx] = idx;
                if(g[i][j] == '1')
                    res++;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int idx = i * m + j;
                if (g[i][j] == '1') {
                    // 合并岛屿
                    if (i + 1 < n && g[i + 1][j] == '1') { 
                        union(idx, (i + 1) * m + j);
                    }
                    if (j + 1 < m && g[i][j + 1] == '1') {
                        union(idx, i * m + j + 1);
                    }
                }
            }
        }

        return res;
    }
}