跳到主要内容

LeetCode 200. 岛屿数量

本节目标

扫描网格中的陆地，并用原地 DFS 一次淹没一个四连通岛屿。

这是图的表示与遍历中“网格就是隐式图”的连通分量母题。它与第六章的网格搜索共享上下左右枚举和边界判断，但这里的目标是统计所有连通块：外层扫描发现一块新陆地后，内层 DFS 必须把整块岛屿全部处理完，而不是搜索某一条目标路径。

查看 LeetCode 原题

题意与约束​

字符 '1' 表示陆地、'0' 表示水，只按上下左右四个方向相连。返回岛屿数。空网格没有岛屿；对角接触的两块陆地并不连通。

直接思路与瓶颈​

对每个陆地格都重新做一次泛洪搜索，再比较能否与之前的陆地相连，会让同一座岛被反复遍历。若有一大片陆地，重复搜索可退化到接近平方级的访问次数。

图模型与算法推导​

逐格扫描。遇到 '0' 直接跳过；遇到尚未处理的 '1'，它必是一个新岛屿的第一个发现点，因此答案加一。将它立即改写为 '0' 并压栈，随后把四邻域中的陆地也在压栈前改写为水。内层栈清空时，这个连通块恰好被完整淹没。

正确性依据​

不变量是：栈中坐标属于当前正在淹没的岛屿，且所有已改为 '0' 的陆地不会再次入栈。每次启动 DFS 前的起点与此前岛屿不连通，否则早已被之前的 DFS 淹没；一次 DFS 恰好覆盖起点所在的整个四连通分量。因此外层每次计数对应一个不同岛屿，每个岛屿也必会在其第一个未处理格被计数一次。

样例执行过程​

以网格 [["1","1","0"],["1","0","0"],["0","0","1"]] 为例。扫描到 (0,0) 时答案从 0 变为 1，先将它改成 0，stack = [(0,0)]；弹出它后，(1,0)、(0,1) 都会在入栈前改为 0，两个邻居均进入栈。C++ 与 Python 的方向枚举顺序不同，具体弹出顺序不影响结果：两个位置的四邻域都没有未淹没陆地，处理后栈清空，左上连通块完全变水。扫描继续到 (2,2)，答案变为 2；该格经入栈、弹出后也被完整处理，最终返回 2。

代码实现​

C++17
#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int rows = grid.size();
        int cols = rows == 0 ? 0 : grid[0].size();
        int islands = 0;
        const int directions[5] = {0, 1, 0, -1, 0};

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (grid[row][col] != '1') continue;
                ++islands;
                vector<pair<int, int>> stack{{row, col}};
                grid[row][col] = '0';
                while (!stack.empty()) {
                    auto [currentRow, currentCol] = stack.back();
                    stack.pop_back();
                    for (int direction = 0; direction < 4; ++direction) {
                        int nxtRow = currentRow + directions[direction];
                        int nxtCol = currentCol + directions[direction + 1];
                        if (nxtRow < 0 || nxtRow >= rows || nxtCol < 0 || nxtCol >= cols ||
                            grid[nxtRow][nxtCol] != '1') {
                            continue;
                        }
                        grid[nxtRow][nxtCol] = '0';
                        stack.push_back({nxtRow, nxtCol});
                    }
                }
            }
        }
        return islands;
    }
};

实现复用输入网格作为 visited 标记。行为测试在每个用例前深拷贝网格，保证前一个用例的原地改写不会污染后一个用例。

复杂度分析​

每个格至多入栈和处理一次，时间复杂度为 O(mn)。显式栈最坏存放一个连通块，额外空间为 O(mn)；原地标记不再另开 visited 数组。

边界与易错点​

  • 只能向四个正交方向扩张，不能把对角格当作邻居。
  • 陆地在入栈前改成水，避免两个相邻格重复压入同一位置。
  • 空网格要先处理行数，不能直接读取第一行。
  • 若题目要求保留输入，应使用独立 visited 数组，不能原地改写。

模式迁移​

把“启动一次 DFS 就加一”的外层循环保留，可迁移到封闭岛屿、最大岛屿面积和省份数量；若目标变为到达边界的最短步数，则应改用 BFS，并让队列层数表示距离。