网格与图上的深度优先搜索（DFS）
二叉树章节中已经介绍了树上的 DFS（前中后序遍历）。本章聚焦 DFS 在网格和一般图上的应用。核心区别在于：树天然无环、方向单一（父→子），而网格/图可能从多个方向重复到达同一节点，因此必须引入 visited 机制来避免死循环。
与回溯算法的关系：两者底层都是 DFS，但目的不同——回溯是在隐式决策树上穷举所有方案（选择→递归→撤销选择），网格 DFS 是在显式图/网格上搜索连通区域（访问→标记→扩展，不撤销标记）。
前置知识
网格 DFS 框架
网格上的 DFS 本质是多叉树遍历（每个格子有 2~8 个邻居），加上越界判断和 visited 标记：
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
function dfs(grid: number[][], row: number, col: number) {
if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length) return;
if (grid[row][col] !== target) return;
// 标记已访问（两种方式二选一）
grid[row][col] = markValue; // 原地修改（"淹没"）
for (const [dr, dc] of directions) {
dfs(grid, row + dr, col + dc);
}
}两种 visited 策略
| 策略 | 做法 | 优点 | 缺点 |
|---|---|---|---|
| 原地修改（淹没） | 将已访问格子的值改为非目标值 | 不需要额外空间 | 会修改原数组 |
| visited 数组 | 维护独立的布尔数组 | 不修改原数组 | O(M×N) 额外空间 |
多数岛屿类问题允许原地修改，优先使用淹没策略。如果题目要求不能修改输入，或同一格子需要被不同起点重复访问，则使用 visited 数组。
与回溯的关键区别：是否撤销标记
回溯需要在递归返回后撤销选择（path.pop()、visited[i] = false），因为同一个元素可能出现在不同方案中。而网格 DFS 不撤销标记——格子一旦被标记为已访问，就不再属于后续任何连通分量。这正是两者的本质差异。
解题决策树
拿到一道网格/图 DFS 题
│
├─ 需要计数或度量连通区域？
│ ├─ 数连通分量个数？
│ │ └─ 遍历网格 + 每次 DFS 启动时计数 .... → 见「一」
│ │
│ └─ 求单个连通区域的属性（面积等）？
│ └─ DFS 中累计属性值 .................. → 见「一」
│
├─ 需要从边界入手排除/标记？
│ └─ 先从边界 DFS 标记，再处理内部 ......... → 见「二」
│
└─ 涉及多个网格对比（子岛屿等）？
└─ 同步遍历两个网格做判断 ............... → 见「三」一、Flood Fill 与连通分量
判断关键词：岛屿数量、最大面积、连通区域、图像渲染、省份数量。
适用场景：在网格或邻接图中，寻找、计数或度量连通区域。
这是网格 DFS 最经典的应用。核心思路：遍历每个格子，遇到未访问的目标格子就启动一次 DFS，将整个连通区域标记为已访问。每次启动 DFS 就对应一个连通分量。
let count = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') {
dfs(grid, r, c); // 淹没整个连通区域
count++; // 一次 DFS = 一个岛屿
}
}
}如果需要度量连通区域的属性（如面积），让 DFS 返回值即可：
function dfs(grid: number[][], r: number, c: number): number {
if (r < 0 || c < 0 || r >= rows || c >= cols) return 0;
if (grid[r][c] === 0) return 0;
grid[r][c] = 0; // 淹没
let area = 1;
for (const [dr, dc] of directions) {
area += dfs(grid, r + dr, c + dc);
}
return area;
}题型参考（框架微调）：
| 题目 | 在 Flood Fill 框架上的微调点 |
|---|---|
[200] 岛屿数量 | 标准框架，每次 DFS 启动时 count++。 |
[695] 岛屿的最大面积 | DFS 返回面积（每访问一个格子 +1），取全局最大值。 |
[733] 图像渲染 | 从指定起点出发，将连通区域的值统一替换为新颜色。 |
[547] 省份数量 | 输入从网格变为邻接矩阵，但连通分量计数逻辑不变。 |
二、边界 DFS
判断关键词：被围绕的区域、封闭岛屿、飞地、从边界出发。
适用场景：需要区分"与边界相连"和"完全被包围"的区域。
正面判断"是否被完全包围"很难——DFS 过程中无法预知未来是否会碰到边界。反向思路更简单：先从边界出发，用 DFS 标记所有与边界相连的区域，剩下未被标记的就是被完全包围的。
// 第一步：从四条边界出发，标记所有与边界相连的目标区域
for (let r = 0; r < rows; r++) {
dfs(grid, r, 0); // 左边界
dfs(grid, r, cols - 1); // 右边界
}
for (let c = 0; c < cols; c++) {
dfs(grid, 0, c); // 上边界
dfs(grid, rows - 1, c); // 下边界
}
// 第二步：处理内部——未被标记的目标区域即为"被包围"的题型参考（框架微调）：
| 题目 | 在边界 DFS 框架上的微调点 |
|---|---|
[130] 被围绕的区域 | 边界 DFS 标记 'O' 为临时值，最后将剩余 'O' 变 'X'，临时值还原 'O'。 |
[1254] 统计封闭岛屿的数目 | 边界 DFS 淹没与边界相连的陆地，再用标准计数统计剩余岛屿。 |
[1020] 飞地的数量 | 边界 DFS 淹没后，计数剩余未被淹没的陆地格子数。 |
三、多网格对比：子岛屿
判断关键词：子岛屿、两个网格对比、同步遍历。
适用场景：给定两个网格，判断一个网格中的岛屿是否是另一个网格中岛屿的子集。
核心思路：遍历网格 B 中的岛屿时，同步检查网格 A 中对应位置是否也是陆地。如果 B 的某个岛屿中存在 A 为水的格子，则该岛屿不是子岛屿。
function dfs(r: number, c: number): boolean {
if (r < 0 || c < 0 || r >= rows || c >= cols) return true;
if (grid2[r][c] === 0) return true;
grid2[r][c] = 0; // 淹没
// 关键：即使当前不匹配，也必须继续 DFS 淹没整个岛屿，避免重复计数
let isSubIsland = grid1[r][c] === 1;
for (const [dr, dc] of directions) {
if (!dfs(r + dr, c + dc)) isSubIsland = false;
}
return isSubIsland;
}题型参考（框架微调）：
| 题目 | 在多网格框架上的微调点 |
|---|---|
[1905] 统计子岛屿 | 标准多网格对比，DFS 中同步检查两个网格的对应位置。 |
总结：解题速查表
| 题型 | 核心策略 | 典型题目 |
|---|---|---|
| 连通分量计数 | 遍历网格 + Flood Fill 计数 | [200] [547] |
| 连通区域属性 | DFS 返回值累计面积/属性 | [695] [733] |
| 边界排除 | 先从边界 DFS，再处理内部 | [130] [1254] [1020] |
| 多网格对比 | 同步遍历两个网格 | [1905] |