#200

中等

高频

动态规划

岛屿数量

这是一道围绕算法展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

算法

原题练习

题目分析

给你一个由字符 '1' 和 '0' 组成的二维网格。

其中 '1' 表示陆地，'0' 表示水域。相邻的陆地如果上下左右连通，就属于同一座岛屿。

要求你统计网格里一共有多少座岛屿。

一句话概括：

在二维网格里，统计有多少块彼此独立的连通陆地区域。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：遍历网格时，只要遇到一块新陆地，就从它出发把整座岛一次性染掉，答案加一。

推荐代码

推荐解法：动态规划

时间复杂度： O(mn)

空间复杂度： O(mn)

核心思路：遍历网格时，只要遇到一块新陆地，就从它出发把整座岛一次性染掉，答案加一。

class Solution {
    // dfs深度遍历的作用就是将统计过的岛屿值设为0
    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;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题本质是在网格里统计连通块数量，我会用 DFS 做 flood fill。

核心过程

先双重循环扫描整个网格。
每次遇到一块还没处理过的陆地，就说明发现了新岛屿，答案加一。
然后从这个格子出发做 DFS，把与它上下左右连通的所有陆地都标记掉。
这样整张图扫完后，答案就是岛屿数量。

复杂度总结

时间复杂度 O(mn)，空间复杂度 O(mn)，最坏情况下递归栈会达到整个网格规模。

面试补一句：看到“统计区域数量”，先别急着想花活，优先联想到连通块计数。

核心思路

这题本质是在二维网格里统计连通块数量。推荐解法用 DFS 从每个新岛屿起点出发，把同一块陆地全部标记掉，避免重复计数。

步骤讲解

先遍历整个网格

用双重循环扫描所有格子，寻找还没处理过的陆地。

为什么这样做：只有先找到每座岛的起点，后续的整块搜索才有入口。

对应代码提示：for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { ... } }

遇到新陆地就计数加一

当 grid[i][j] == '1' 时，说明发现了一座新的岛屿。

为什么这样做：只有第一次遇到这座岛时才应该计数，后续都应被标记掉而不是再次统计。

对应代码提示：if (grid[i][j] == '1') { count++; dfs(...); }

用 DFS 把整座岛染掉

从当前陆地格子出发，递归访问上下左右所有连通的陆地，并把它们改成 0。

为什么这样做：这样后面再扫到这些格子时，就不会被误认为是新岛屿。

对应代码提示：grid[row][col] = '0';

递归里先做越界和水域判断

如果坐标越界，或者当前格子不是陆地，递归立即返回。

为什么这样做：DFS 必须有明确的终止条件，否则会访问非法位置或无限展开。

对应代码提示：if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] != '1') return;

只向四个方向扩张

从当前格子继续访问上、下、左、右四个相邻位置。

为什么这样做：题目定义的连通关系只有四联通，对角线不算同一座岛。

对应代码提示：dfs(row - 1, col); dfs(row + 1, col); dfs(row, col - 1); dfs(row, col + 1);

易错点

把陆地个数误当成岛屿个数

题目统计的是连通块数量，不是字符 1 的总数。

正确理解：每发现一块新陆地，只计数一次，然后立刻把整块区域全部搜索掉。

忘记标记访问过的格子

如果 DFS 访问完不染色，后面的遍历还会把同一座岛再次算进去。

正确理解：访问到陆地后，第一时间改成 0 或使用独立 visited 数组。

把对角线当成连通

很多人会下意识把八个方向都看成相邻，但这题只允许上下左右连通。

正确理解：搜索时严格只扩四个方向。

复杂度与适用判断

时间复杂度：O(mn)

空间复杂度：O(mn)

比其他方案更好在哪里：比每次重复扫描局部区域更直接，能保证每个格子最多只处理一次。

适用判断：矩阵里出现“岛屿、区域、连通块、染色”这类关键词时，优先考虑 DFS/BFS。

额外提醒

这道题是二维网格 DFS/BFS 染色的代表题，迁移性很强。
套路固定：找到起点，计数加一，整块清掉。

动画演示

如果你还没完全看懂，可以展开动画演示。

动态规划动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

岛屿数量 - DFS算法

当前岛屿数量: 0

步骤: 1 / 0

水域

未访问陆地

正在访问

已访问陆地

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。