岛屿数量 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

先说总体思路，然后说 DFS 的细节。

总体思路

看示例 2：

假设你是哥伦布。先从左上角开始，把第一个岛全部插上旗子🚩，这里用 $2$ 表示。插满旗子后，把答案（岛屿个数）加一。

⚠注意：在岛上，你只能左右上下走，不能斜方向走。

继续遍历，寻找其他的岛屿，也就是 $1$ 。找到 $1$ 意味着发现了一个新的岛，继续插上旗子🚩，把答案加一。

继续遍历，寻找其他的岛屿。找到 $1$ 意味着发现了一个新的岛，插满旗子🚩，把答案加一。

如果没有 $1$ 了，算法就结束了，返回答案（岛屿个数）。

如何实现？

一旦我们发现 $(i, j)$ 是 $1$ ，就从 $(i, j)$ 开始，DFS 这个岛。

每一步可以往左右上下四个方向走，也就是

(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)

这四个格子。

如果到达一块未发现的陆地格子，就插上旗子🚩，把 $grid [i] [j]$ 改成 $2$ 。

如果 $(i, j)$ 出界，或者 $(i, j)$ 是水，或者 $(i, j)$ 已发现（已插上旗子🚩），就不再继续往下递归。

⚠注意：DFS 的过程中，最重要的是不能重复访问之前访问过的格子。

比如从左上角 $(0, 0)$ 向右移动到 $(0, 1)$ ，然后从 $(0, 1)$ 又向左移动到 $(0, 0)$ ，再从 $(0, 0)$ 向右移动到 $(0, 1)$ ，如此往复，就无限递归下去了。

怎么避免重复访问？本题的做法是把访问过的格子都插上旗子🚩。例如从 $(0, 1)$ 往左走，发现 $(0, 0)$ 是插过旗子的格子，就不继续走了。

答疑

问：二叉树的递归和网格图的递归有何区别？

答：列表总结如下。

	二叉树	网格图
递归入口	根节点	岛屿第一行最左边的陆地
递归方向	左儿子和右儿子	左右上下的相邻陆地
递归边界	空节点（或者叶节点）	出界、遇到水或者旗子

问：如何理解递归？

答：递归的思想是，假设你是一家公司的老板，你不需要万事亲力亲为，而是拆解问题，交给下属去做。对于这题来说，就是从岛屿的某个位置登陆插旗，然后一分为四，把探索整个岛屿的任务交给其他人去处理，自己只需处理好第一步就行。

问：我可以先判断 $grid [i] [j]$ 是否等于 $1$ ，再判断 $(i, j)$ 是否出界吗？

问：不行，比如 $i = - 1$ ，获取 $grid [i] [j]$ 就下标越界了。要先保证下标在范围中，再去获取数组元素值。

问：我可以把访问过的 $grid [i] [j]$ 改成 $0$ 吗？

答：可以。相当于把访问过的位置变成水。其实，改成除了 $1$ 以外的任何值都行。

问：我可以把这行代码 grid[i][j] = '2' 写在 $dfs$ 的最后一行吗？

答：不行。这样写会先执行递归，比如从左上角 $(0, 0)$ 向右移动到 $(0, 1)$ ，内部继续递归，从 $(0, 1)$ 又向左移动到 $(0, 0)$ ，导致反复横跳，无限递归。

问：DFS 中能否只考虑往右走和往下走？

答：不行，比如蚊香形的岛屿，在探索的时候必须具备左右上下走的能力。

Python 解法1C++ 解法1

python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(i: int, j: int) -> None:
            # 出界，或者不是 '1'，就不再往下递归
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
                return
            grid[i][j] = '2'  # 插旗！避免来回横跳无限递归
            dfs(i, j - 1)  # 往左走
            dfs(i, j + 1)  # 往右走
            dfs(i - 1, j)  # 往上走
            dfs(i + 1, j)  # 往下走

        ans = 0
        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                if c == '1':  # 找到了一个新的岛
                    dfs(i, j)  # 把这个岛插满旗子，这样后面遍历到的 '1' 一定是新的岛
                    ans += 1
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        auto dfs = [&](this auto&& dfs, int i, int j) -> void {
            // 出界，或者不是 '1'，就不再往下递归
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
                return;
            }
            grid[i][j] = '2'; // 插旗！避免来回横跳无限递归
            dfs(i, j - 1); // 往左走
            dfs(i, j + 1); // 往右走
            dfs(i - 1, j); // 往上走
            dfs(i + 1, j); // 往下走
        };

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') { // 找到了一个新的岛
                    dfs(i, j); // 把这个岛插满旗子，这样后面遍历到的 '1' 一定是新的岛
                    ans++;
                }
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O (m n)$ ，其中 $m$ 和 $n$ 分别是 $grid$ 的行数和列数。由于 DFS 中修改了 grid[i][j] = '2'，当我们访问一个访问过的格子时，会触发 if grid[i][j] != '1': return。只有首次访问一个格子时，才会继续递归，其余情况不会继续递归。每次插上一个旗子只需要 $O (1)$ 的时间，插上至多 $m n$ 个旗子，就需要 $O (m n)$ 的时间。
空间复杂度： $O (m n)$ 。最坏情况下，对于蛇形陆地、蚊香型陆地等，递归需要 $O (m n)$ 的栈空间。

思考题

构造一个 $grid$ ，让上面代码的递归深度达到最大。
如果调整四个方向的递归顺序（比如顺序为右下左上），递归路径的形状会发生什么变化？

欢迎在评论区分享你的思路。

专题训练

见下面的网格图题单。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

总体思路 ​

如何实现？ ​

答疑 ​

复杂度分析 ​

思考题 ​

专题训练 ​

分类题单 ​

总体思路

如何实现？

答疑

复杂度分析

思考题

专题训练

分类题单