🧱[NC]109. 岛屿数量 【DFS、BFS、并查集】

🚩传送门：牛客题目

题目

给你一个由 **'1'**（陆地）和 **'0'**（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [ [“1”,”1”,”1”,”1”,”0”], [“1”,”1”,”0”,”1”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”0”,”0”,”0”] ] 输出：1

示例 2：

输入：grid =[ [“1”,”1”,”0”,”0”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”1”,”0”,”0”], [“0”,”0”,”0”,”1”,”1”] ] 输出：3

解题思路：DFS 深度遍历

我们可以将二维网格看成一个无向图，竖直或水平相邻的 之间有边相连。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 ，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 都会被重新标记为 。
最终岛屿的数量就是我们进行深度优先搜索的次数。

下面的动画展示了整个算法。

复杂度分析

时间复杂度：

  - 其中 ![](https://cdn.nlark.com/yuque/__latex/6f5dde593f0bc27956e14b5eaec2ed17.svg#card=math&code=M&id=Z9xKK) 和 ![](https://cdn.nlark.com/yuque/__latex/459f3c80a50b7be28751b0869ef5386a.svg#card=math&code=N&id=FRPQx) 分别为行数和列数。

空间复杂度：

  - 在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到** **![](https://cdn.nlark.com/yuque/__latex/ddf2bad2744e10a12a1796517806206f.svg#card=math&code=M%C2%B7N&id=ci0CJ)。

官方代码

class Solution {
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
}

解题思路：BFS 广度遍历

同样地，我们也可以使用广度优先搜索代替深度优先搜索。

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 ，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 都会被重新标记为 。直到队列为空，搜索结束。

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

复杂度分析

时间复杂度：

  - 其中 _**M**_ 和 _**N**_ 分别为行数和列数。

空间复杂度：

  - 在最坏情况下，整个网格均为陆地，队列的大小可以达到** **![](https://cdn.nlark.com/yuque/__latex/fc664a9ff33255ecc4841274b336d7ec.svg#card=math&code=%5Csmall%20O%28%5Cmin%28M%2C%20N%29%29&height=23&id=RrqQj)。

官方代码

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;

        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    grid[r][c] = '0';
                    Queue<Integer> neighbors = new LinkedList<>();
                    neighbors.add(r * nc + c);
                    while (!neighbors.isEmpty()) {
                        int id = neighbors.remove();
                        int row = id / nc;
                        int col = id % nc;
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
                            neighbors.add((row-1) * nc + col);
                            grid[row-1][col] = '0';
                        }
                        if (row + 1 < nr && grid[row+1][col] == '1') {
                            neighbors.add((row+1) * nc + col);
                            grid[row+1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
                            neighbors.add(row * nc + col-1);
                            grid[row][col-1] = '0';
                        }
                        if (col + 1 < nc && grid[row][col+1] == '1') {
                            neighbors.add(row * nc + col+1);
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }

        return num_islands;
    }
}