0200. Number of Islands ======================= 题目信息 -------- :题号: 0200. 岛屿数量 :难度: Medium :主题: 网格、连通分量、深度优先搜索、原地标记 :原题: `LeetCode 0200 `_ :重点: 把陆地格视为隐式图节点,每次发现未访问陆地就计数并完整清除其四邻接分量 题目重述 -------- 给定只包含字符 ``'0'``、``'1'`` 的矩形网格,``'1'`` 表示陆地,``'0'`` 表示水。上下 左右相邻的陆地属于同一岛屿,对角接触不算连通。返回岛屿数量。 主解允许把访问过的陆地原地改为水,因此调用后输入网格会被修改。 自建示例 -------- .. code-block:: text 输入: 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 输出:3 左上、中央、右下分别是三个四邻接连通分量。 .. code-block:: text 输入: 1 0 0 1 输出:2 两格只在对角线接触,不属于同一岛屿。 .. code-block:: text 输入:全水网格 输出:0 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { public: int numIslands(std::vector>& grid) { if (grid.empty() || grid[0].empty()) { return 0; } int rows = static_cast(grid.size()); int columns = static_cast(grid[0].size()); const int row_step[4] = {1, -1, 0, 0}; const int column_step[4] = {0, 0, 1, -1}; std::vector> 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。 具体状态走读 ~~~~~~~~~~~~ 考虑: .. code-block:: text 1 1 0 0 1 0 0 0 1 #. 扫描 ``(0,0)``,计数变 1,先将其清零并压栈; #. 扩展到 ``(0,1)``,再从那里扩展到 ``(1,1)``。三格全部清零后栈为空; #. 外层经过这些位置时只看到水,不再重复计数; #. 扫描到 ``(2,2)`` 时它仍为陆地。它与 ``(1,1)`` 仅对角接触,所以启动第二次洪泛, 最终答案为 2。 全陆网格在第一个格子处启动一次洪泛并清除所有格,答案为 1;全水网格从不进入计数分支, 答案为 0。空网格防御分支避免访问不存在的第一行。 正确性与方案取舍 ~~~~~~~~~~~~~~~~ 一次 DFS 访问且仅访问起点的完整四邻接分量;外层遇到的每个残留 ``'1'`` 都属于尚未计数 的新分量。每个岛至少有一个最先扫描到的格子触发计数,洪泛后同岛其余格不再触发,因此每 个岛恰好计数一次。 递归 DFS 能表达相同洪泛,但最多 ``300*300`` 的狭长陆地可能产生很深调用栈;BFS 队列也 同样正确。主解使用显式 ``vector`` 作为栈,避免递归深度风险,并保持深度优先处理顺序。 外层扫描每格一次,每个陆地格最多入栈、出栈并检查四邻居一次,时间复杂度为 ``O(mn)``。 显式栈最坏保存 ``O(mn)`` 个坐标,不能因省去 ``visited`` 就声称常数空间;额外访问矩阵 空间为零,但工作前沿仍可能线性增长。