外观
岛屿数量面试标准解：DFS 淹没法从会写到写对
问题背景：为什么岛屿数量是图论题
LeetCode 200「岛屿数量」几乎是网格图面试的入门必考题。题目给出一个由 '1'（陆地）和 '0'（水域）组成的二维网格，要求统计岛屿数量。这里的岛屿定义为：通过水平或垂直方向相邻的陆地连接形成的区域，斜向相邻不算连通。
很多初学者把它当成“遍历二维数组并计数”，结果越写越乱。本质上，这是一个典型的无向图连通分量计数问题：
- 每个值为
'1'的格子是一个图节点； - 上下左右四个方向代表节点之间的边；
- 一次 DFS 或 BFS 能访问完一个岛屿中的全部陆地；
- 启动了多少次搜索，就有多少个连通分量。
所谓“淹没标记法”，是在访问陆地后立刻把它改成水域 '0'，相当于把已访问节点从图中删除。这样不需要额外维护 visited 集合，也能保证每个格子只被处理一次。
方案对比：DFS、BFS 与并查集怎么选
常见标准解法有三类。
| 方案 | 核心思路 | 优点 | 注意点 |
|---|---|---|---|
| 网格 DFS | 从陆地出发递归淹没整座岛 | 代码短、面试表达清晰 | 网格极大时可能递归栈溢出 |
| 网格 BFS | 用队列逐层扩展陆地 | 避免递归深度问题 | 入队时就要标记访问 |
| 并查集 | 合并相邻陆地，最后统计集合数 | 适合动态连通性扩展 | 本题代码量相对更大 |
对静态网格的岛屿数量，DFS 淹没法是最常见的面试标准答案；如果面试官追问递归深度，可主动给出 BFS 或显式栈迭代 DFS。
实操步骤：递归 DFS 淹没标记法
标准做法分两层：
- 外层双重循环扫描每一个格子；
- 当遇到未访问的陆地
'1'，说明发现一座新岛，答案加一； - 从该格子启动 DFS，将当前格子标记为
'0'； - 递归访问上下左右四个方向；
- 搜索结束后，这座岛的所有陆地都已被淹没，不会被重复计数。
下面代码可直接运行：
python
from typing import List
def num_islands(grid: List[List[str]]) -> int:
"""统计二维网格中的岛屿数量。"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def dfs(r: int, c: int) -> None:
# 越界或当前格子不是陆地，直接返回
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != "1":
return
# 关键：先淹没当前格子，再递归扩展，避免重复访问
grid[r][c] = "0"
for dr, dc in directions:
dfs(r + dr, c + dc)
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
count += 1
dfs(r, c)
return count
# 可直接运行的测试用例
grid = [
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"],
]
print(num_islands(grid)) # 输出：3为什么改成 '0' 就等价于 visited
DFS 最容易出现的问题是重复访问。假设 A 格子访问了右边的 B，B 又尝试访问左边的 A，如果 A 没有被标记，程序会在两个节点之间无限递归。
把当前陆地改成 '0' 后：
- 它不会再次触发外层计数；
- 邻居递归到它时会被
grid[r][c] != "1"拦截； - 每个格子最多进入一次有效 DFS。
因此，原地修改输入虽然节省了 visited 空间，但也改变了原网格。若题目明确要求保留输入，应使用访问数组，或先复制网格。
BFS 写法：避免长路径递归深度问题
当整张网格都是陆地且规模很大时，递归 DFS 的调用深度可能达到格子数量级别，部分语言环境会触发栈溢出。BFS 使用队列保存待访问节点，更适合说明你考虑了工程边界。
python
from collections import deque
from typing import List
def num_islands_bfs(grid: List[List[str]]) -> int:
"""使用 BFS 统计岛屿数量。"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != "1":
continue
count += 1
grid[r][c] = "0"
queue = deque([(r, c)])
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == "1":
# 入队前必须立即标记，否则同一格子可能被重复加入队列
grid[nx][ny] = "0"
queue.append((nx, ny))
return countBFS 与 DFS 的时间复杂度完全相同，区别主要在空间使用形式：DFS 依赖递归调用栈，BFS 依赖队列。队列最大长度通常取决于网格宽度或某一层边界规模。
复杂度分析
设网格行数为 m，列数为 n，格子总数为 m × n。
- 时间复杂度：
O(mn)。每个格子在外层循环中被扫描一次；陆地格子最多被搜索一次；水域不会进入 DFS/BFS。 - 空间复杂度：
O(mn)。最坏情况下整张网格都是陆地，递归栈或队列可能容纳O(mn)个节点；平均情况通常小于该上界。 - 额外标记空间：
O(1)。淹没法直接修改原网格，没有单独的visited数组，但代价是输入被破坏。
面试时建议主动说明：如果不能修改输入，应新增 visited: List[List[bool]]，此时额外空间为 O(mn)。
变体扩展：从标准答案到举一反三
掌握连通分量模板后，很多网格题只是判定条件和统计目标发生变化：
- 岛屿最大面积：DFS 返回当前连通分量大小，取最大值；
- 封闭岛屿数量：边界上的陆地不算封闭，需要先淹没边界连通区域；
- 飞地数量：统计无法从边界到达的陆地格子数；
- 被围绕的区域：从边界的
'O'做 BFS 标记，再翻转未标记区域； - 岛屿数量 II：逐步填海并动态查询连通分量数，并查集更合适。
这些题的共同点仍是：先定义节点和连通方向，再决定搜索起点、访问标记和答案统计时机。
避坑总结：面试中最容易丢分的细节
1. 字符和数字类型混淆
常见错误是把网格元素写成数字判断：
python
# 错误：题目输入通常是字符 "1"，不是整数 1
if grid[r][c] == 1:
count += 1修正方法是严格按照输入类型判断 "1" 和 "0"。如果面试中输入可能是整数矩阵，应先和面试官确认，再统一比较条件。
2. 递归后才标记导致重复访问或死循环
错误写法先递归四个方向，最后才把当前格子设为 '0'。这样相邻格子会再次访问当前格子，调用链无法终止。正确顺序是：进入格子后立即标记，再向四方向扩展。
3. BFS 出队时才标记，队列可能指数膨胀
很多人写 BFS 时在 popleft() 后才设置访问标记。问题是同一个陆地可能被上方、左方邻居重复加入队列，造成大量重复节点。修正方法是在发现合法邻居并加入队列的瞬间标记为 '0'。
4. 忘记处理空网格
直接访问 grid[0] 在空列表时会抛出索引异常。函数开头应判断：
python
if not grid or not grid[0]:
return 05. 把斜向相邻误认为连通
岛屿数量默认只考虑上下左右，方向数组应只有四个元素。若误加入四个对角方向，会把本不相连的岛屿合并。只有题目明确说明八方向连通时，才使用八个方向。
6. 忽视原地修改输入的副作用
淹没法代码最短，但调用函数后原网格会全部变成水域视角。若后续还要使用原始地图，必须复制输入或使用独立访问数组。面试中主动指出这一点，往往比只写出答案更能体现工程意识。
结语
岛屿数量的标准解并不复杂，但它非常适合考察候选人是否能把网格抽象成图、是否真正理解 DFS/BFS 的访问时机，以及是否能分析最坏复杂度。记住核心模板：外层扫描发现新岛屿，内层搜索淹没整个连通分量；计数只在搜索启动时发生一次。按这个框架表达，既能快速写出代码，也能自然应对面积、边界、动态连通等变体题。
免责声明
本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。