0200. Number of Islands

题目信息

题号:
  1. 岛屿数量

难度:

Medium

主题:

网格、连通分量、深度优先搜索、原地标记

原题:

LeetCode 0200

重点:

把陆地格视为隐式图节点,每次发现未访问陆地就计数并完整清除其四邻接分量

题目重述

给定只包含字符 '0'、'1' 的矩形网格,'1' 表示陆地,'0' 表示水。上下 左右相邻的陆地属于同一岛屿,对角接触不算连通。返回岛屿数量。

主解允许把访问过的陆地原地改为水,因此调用后输入网格会被修改。

自建示例

输入:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出:3

左上、中央、右下分别是三个四邻接连通分量。
输入:
1 0
0 1

输出:2

两格只在对角线接触,不属于同一岛屿。
输入:全水网格
输出:0

C++ 实现

#include <utility>
#include <vector>

class Solution {
public:
    int numIslands(std::vector<std::vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) {
            return 0;
        }

        int rows = static_cast<int>(grid.size());
        int columns = static_cast<int>(grid[0].size());
        const int row_step[4] = {1, -1, 0, 0};
        const int column_step[4] = {0, 0, 1, -1};
        std::vector<std::pair<int, int>> pending;
        int islands = 0;

        for (int row = 0; row < rows; ++row) {
            for (int column = 0; column < columns; ++column) {
                if (grid[row][column] != '1') {
                    continue;
                }

                ++islands;
                grid[row][column] = '0';
                pending.push_back({row, column});

                while (!pending.empty()) {
                    auto [current_row, current_column] = pending.back();
                    pending.pop_back();

                    for (int direction = 0; direction < 4; ++direction) {
                        int next_row =
                            current_row + row_step[direction];
                        int next_column =
                            current_column + column_step[direction];

                        if (next_row >= 0 && next_row < rows &&
                            next_column >= 0 && next_column < columns &&
                            grid[next_row][next_column] == '1') {
                            grid[next_row][next_column] = '0';
                            pending.push_back({next_row, next_column});
                        }
                    }
                }
            }
        }
        return islands;
    }
};

题解

逐格统计数错在对象粒度

统计字符 '1' 的数量得到的是陆地面积,不是岛屿数量;一个岛可以包含任意多个陆地格。 若每遇到一个陆地就向前搜索它是否与某个已计数格相连,会在不同起点间反复遍历同一片区域。

把每个陆地格看作图节点,上下左右相邻陆地之间存在边,岛屿就是这个隐式无向图的一个极大 连通分量。连通分量计数的标准结构是:扫描全部节点,发现一个未访问节点时计数一次,并在 继续扫描前访问完它所在的整个分量。

一次洪泛删除一个完整搜索空间

外层按行、列扫描。遇到仍为 '1' 的格子,它不可能属于此前发现的岛:若属于,先前从 同岛起点进行的洪泛已经到达并标记它。因此这格必然是一个新连通分量的首次发现, islands 加一。

随后用显式栈从该格开始 DFS。每弹出一个格子,只检查上、下、左、右四个方向;仍为陆地的 邻居被标记并压栈。栈耗尽时:

  • 所有访问到的格子都通过四邻接路径连到起点,不会跨水吞并别岛;

  • 与起点四邻接连通的所有陆地,也会沿某条路径逐步被发现,不会遗漏;

  • 整个岛已经从后续外层扫描的候选中删除。

因此一次计数对应一次完整洪泛,而不是一个陆地格。

原地标记代替 visited

正常图遍历需要 visited 集合。输入只有水、陆地两种字符,算法可以把已发现陆地立即从 '1' 改成 '0',让判断 grid[next] == '1' 同时表示“这是陆地”与“尚未访问”。

这样删除了 m x n 的布尔矩阵,代价是破坏输入。如果调用方之后还需要原网格,应在 调用前复制;主解的接口和正文明确接受原地修改,不能把这项副作用隐藏起来。

为什么在压栈前标记

同一陆地可能同时邻接多个已发现格。若等到弹出时才标记,它在第一次被处理前可能被多个 邻居重复压栈,增加无用状态,甚至让空间显著膨胀。

代码在发现邻居时先写 '0',再压栈。从这一刻起,任何其他方向再次看到该坐标都不再 满足入栈条件,所以每个陆地格最多入栈一次。起点也遵循同样顺序:先标记,再进入工作栈。

栈循环的不变量

一次洪泛期间始终保持:

  • pending 中的坐标原本都是陆地,已经标记为 '0',且与本次起点连通;

  • 已弹出的坐标已经检查完四个邻居;

  • 当前岛中已经发现但尚未扩展的格子都在栈中;

  • 仍为 '1' 的格子尚未被任何洪泛发现。

方向数组只含 (1,0)、(-1,0)、(0,1)、(0,-1)。没有对角方向,所以 [[1,0],[0,1]] 的第一次洪泛无法到达右下角;外层稍后仍会看到第二个 '1' 并再次 计数,得到 2。

具体状态走读

考虑:

1 1 0
0 1 0
0 0 1
  1. 扫描 (0,0),计数变 1,先将其清零并压栈;

  2. 扩展到 (0,1),再从那里扩展到 (1,1)。三格全部清零后栈为空;

  3. 外层经过这些位置时只看到水,不再重复计数;

  4. 扫描到 (2,2) 时它仍为陆地。它与 (1,1) 仅对角接触,所以启动第二次洪泛, 最终答案为 2。

全陆网格在第一个格子处启动一次洪泛并清除所有格,答案为 1;全水网格从不进入计数分支, 答案为 0。空网格防御分支避免访问不存在的第一行。

正确性与方案取舍

一次 DFS 访问且仅访问起点的完整四邻接分量;外层遇到的每个残留 '1' 都属于尚未计数 的新分量。每个岛至少有一个最先扫描到的格子触发计数,洪泛后同岛其余格不再触发,因此每 个岛恰好计数一次。

递归 DFS 能表达相同洪泛,但最多 300*300 的狭长陆地可能产生很深调用栈;BFS 队列也 同样正确。主解使用显式 vector 作为栈,避免递归深度风险,并保持深度优先处理顺序。

外层扫描每格一次,每个陆地格最多入栈、出栈并检查四邻居一次,时间复杂度为 O(mn)。 显式栈最坏保存 O(mn) 个坐标,不能因省去 visited 就声称常数空间;额外访问矩阵 空间为零,但工作前沿仍可能线性增长。