从LeetCode 200‘岛屿数量’到蓝桥杯真题：手把手拆解DFS解题的完整思考链路

从LeetCode 200到蓝桥杯真题：DFS解题的思维拆解与实战迁移

当你第一次面对LeetCode 200题"岛屿数量"时，是否感觉无从下手？或者虽然能写出代码，却说不清为何这样设计？本文将以这道经典题为切入点，还原算法高手面对网格类问题的完整思考过程。不同于直接给出标准答案，我们将重点拆解如何将实际问题转化为DFS可解的模型、递归函数设计的底层逻辑以及解题模式的通用迁移方法——这些正是蓝桥杯等算法竞赛考察的核心能力。

1. 问题本质与建模：从网格到图的思维跃迁

面对一个由'1'和'0'组成的二维网格，新手常犯的错误是仅将其视为二维数组。而高手的第一个思维转折点在于：识别出网格本质上是一个隐式图结构。每个陆地格子('1')是图中的节点，相邻（上下左右）的陆地之间存在隐式的边。

# 网格示例（图结构示意） grid = [ ["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "1", "0", "0"], ["0", "0", "0", "1", "1"] ] # 对应图结构： # 节点(0,0)-(0,1)-(1,0)-(1,1)构成连通分量1 # 节点(2,2)自成连通分量2 # 节点(3,3)-(3,4)构成连通分量3

这种转化之所以关键，是因为它将问题归约到了连通分量计数这一经典图论问题。此时DFS的价值凸显出来——它能高效地探索连通区域。思考路径如下：

1. 遍历每个网格单元
2. 发现未访问的'1'时启动DFS
3. 通过DFS标记所有相连的'1'为已访问
4. 岛屿数=启动DFS的次数

提示：在竞赛中，能否快速建立这种问题转化思维，往往决定了能否在有限时间内解题。

2. DFS设计的三层逻辑解剖

2.1 感染机制：避免重复访问的标记策略

直接遍历会导致对同一岛屿的重复计数。高手常用的"感染"策略（将访问过的'1'改为'0'）本质上是隐式标记法，相比显式维护visited数组，这种就地修改的方法：

• 空间复杂度从O(MN)降至O(1)（不考虑递归栈）
• 避免了额外的数据结构维护
• 需要注意题目是否允许修改原数组

def dfs(grid, i, j): # 终止条件：越界或非陆地 if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1': return # "感染"当前单元格 grid[i][j] = '0' # 四向探索 dfs(grid, i+1, j) dfs(grid, i-1, j) dfs(grid, i, j+1) dfs(grid, i, j-1)

2.2 递归参数设计的取舍艺术

观察上述DFS函数，参数设计体现了几个关键考量：

在蓝桥杯C++实现中，通常会传入行列数：

void dfs(vector<vector<char>>& grid, int i, int j, int rows, int cols) { if (i < 0 || j < 0 || i >= rows || j >= cols || grid[i][j] != '1') return; grid[i][j] = '0'; dfs(grid, i+1, j, rows, cols); // ...其他方向 }

2.3 终止条件的完备性检查

递归终止条件必须覆盖所有非法情况：

1. 行索引越界（i < 0 或 i >= rows）
2. 列索引越界（j < 0 或 j >= cols）
3. 当前单元格非陆地（grid[i][j] != '1'）

遗漏任何一项都会导致运行时错误。在竞赛中，建议先用注释列出所有终止条件再编码。

3. 复杂度分析与优化视角

3.1 时间复杂度：O(MN)的必然性

每个单元格最多被访问两次：

• 主循环中的一次检查
• DFS过程中的一次访问

因此时间复杂度严格为O(M×N)。这是理论下限，因为必须检查每个单元格。

3.2 空间复杂度：递归深度的隐藏成本

最坏情况下（整个网格为'1'），递归深度达O(MN)。对于大型网格（如1000×1000），这会导致栈溢出。此时可：

• 改用显式栈的迭代实现
• 使用BFS替代（空间复杂度相同但常数因子更优）
• 在允许情况下修改递归深度限制

迭代DFS示例：

def dfs_iterative(grid, i, j): stack = [(i, j)] while stack: x, y = stack.pop() if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == '1': grid[x][y] = '0' stack.append((x+1, y)) stack.append((x-1, y)) stack.append((x, y+1)) stack.append((x, y-1))

4. 解题模式的通用迁移策略

4.1 蓝桥杯真题中的变形应用

以2021年蓝桥杯省赛"草地灌溉"题为例：

题目变形：计算需要多少水源点才能灌溉所有草地（'G'表示草地，相邻草地可共享水源）

# 解法只需将岛屿数量中的'1'替换为'G' def count_sources(field): count = 0 for i in range(len(field)): for j in range(len(field[0])): if field[i][j] == 'G': count += 1 dfs(field, i, j) return count

4.2 连通性问题解题框架

总结出通用模板：

1. 主循环：遍历每个元素
2. 触发条件：当发现未处理的连通元素时
3. 扩散处理：使用DFS/BFS标记所有连通元素
4. 计数规则：触发次数即为连通分量数

表格对比不同问题的参数调整：

4.3 调试技巧与常见陷阱

在蓝桥杯实战中，DFS实现常遇到：

• 无限递归：终止条件不完整导致
• 错误计数：标记时机不当造成
• 性能超时：未及时剪枝或双重计数

调试检查清单：

1. 终止条件是否覆盖所有非法情况？
2. 标记是在递归前还是递归后进行？
3. 主循环是否跳过已处理元素？
4. 递归方向是否完整（四向/八向）？

以"被围绕的区域"(LeetCode 130)为例，特殊处理边界连通可提升效率：

def solve(board): if not board: return rows, cols = len(board), len(board[0]) # 预处理边界上的'O' for i in range(rows): dfs(board, i, 0) dfs(board, i, cols-1) for j in range(cols): dfs(board, 0, j) dfs(board, rows-1, j) # 后续处理...

这种预处理思维在竞赛中能显著优化时间复杂度。