0200. Number of Islands¶
题目信息¶
- 题号:
岛屿数量
- 难度:
Medium
- 主题:
网格、连通分量、深度优先搜索、原地标记
- 原题:
- 重点:
把陆地格视为隐式图节点,每次发现未访问陆地就计数并完整清除其四邻接分量
题目重述¶
给定只包含字符 '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
扫描
(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 就声称常数空间;额外访问矩阵
空间为零,但工作前沿仍可能线性增长。