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`` 就声称常数空间;额外访问矩阵
空间为零,但工作前沿仍可能线性增长。