当前位置：首页 > news >正文

力扣130题：被围绕的区域DFS/BFS解法与优化

news 2026/8/9 6:36:20

1. 问题背景与核心挑战

今天咱们来啃一块硬骨头——力扣第130题"被围绕的区域"。这道题在面试中的出现频率相当高，尤其喜欢考那些自诩"精通DFS/BFS"的候选人。题目看似简单：给定一个二维矩阵，把所有被'X'完全包围的'O'区域替换为'X'。但实际操作中，90%的候选人都会掉进同一个坑里。

我第一次遇到这个问题是在某大厂终面，当时自信满满地写了个标准DFS，结果面试官微微一笑："如果棋盘是1000×1000呢？"瞬间栈溢出。这道题的精妙之处在于，它考察的不仅是基础算法能力，更是对问题本质的理解和优化思维。

2. 暴力DFS解法与致命缺陷

2.1 最直观的暴力思路

大多数人（包括当年的我）的第一反应是这样的：

遍历整个矩阵
遇到'O'就启动DFS/BFS
检查这个区域是否被'X'完全包围
如果是就全部翻转为'X'

用Python实现的伪代码大概长这样：

def solve(board): if not board: return m, n = len(board), len(board[0]) def dfs(i, j): if 0 <= i < m and 0 <= j < n and board[i][j] == 'O': board[i][j] = '#' dfs(i+1, j) dfs(i-1, j) dfs(i, j+1) dfs(i, j-1) for i in range(m): for j in range(n): if board[i][j] == 'O': # 临时标记为#以便后续处理 dfs(i, j) # 检查是否被包围（需要额外实现check_surrounded函数） if check_surrounded(board, i, j): flip_region(board, '#', 'X') else: flip_region(board, '#', 'O')

2.2 这个解法为什么不行

这个解法有三个致命问题：

栈溢出风险：当矩阵很大时（比如1000×1000全是'O'），递归深度会达到百万级，直接爆栈
重复计算：同一个'O'可能被多个相邻'O'重复访问
逻辑漏洞：边缘的'O'区域永远不会被包围，但上述代码仍会尝试处理

关键教训：在矩阵类问题中，递归实现的DFS往往不是最优解，特别是在面对大规模数据时。面试官设置这样的边界条件，就是为了考察候选人是否考虑到了算法在实际工程中的应用场景。

3. 逆向思维：从边缘突围

3.1 解题思路的重构

经过前面的失败，我们需要换个角度思考：与其费力寻找"被包围的区域"，不如直接找出"没有被包围的区域"——也就是所有与边缘相连的'O'区域。剩下的'O'自然就是被包围的。

具体步骤：

先处理四条边上的'O'，用DFS/BFS标记所有与之相连的'O'
这些被标记的'O'就是存活区域，不应该被翻转
最后遍历整个矩阵：
- 未被标记的'O'→翻转为'X'
- 被标记的'O'→恢复为'O'

3.2 优化后的代码实现

def solve(board): if not board: return m, n = len(board), len(board[0]) def dfs(i, j): if 0 <= i < m and 0 <= j < n and board[i][j] == 'O': board[i][j] = 'S' # S表示Survive dfs(i+1, j) dfs(i-1, j) dfs(i, j+1) dfs(i, j-1) # 处理第一列和最后一列 for i in range(m): if board[i][0] == 'O': dfs(i, 0) if board[i][n-1] == 'O': dfs(i, n-1) # 处理第一行和最后一行 for j in range(n): if board[0][j] == 'O': dfs(0, j) if board[m-1][j] == 'O': dfs(m-1, j) # 最终处理 for i in range(m): for j in range(n): if board[i][j] == 'O': board[i][j] = 'X' elif board[i][j] == 'S': board[i][j] = 'O'

4. 工程优化：用迭代代替递归

4.1 避免栈溢出的BFS实现

虽然上面的解法已经不错，但在极端情况下仍可能栈溢出。更工程化的做法是用显式栈（DFS）或队列（BFS）代替递归。以下是BFS实现：

from collections import deque def solve(board): if not board: return m, n = len(board), len(board[0]) queue = deque() # 将边缘的'O'加入队列 for i in range(m): if board[i][0] == 'O': queue.append((i, 0)) if board[i][n-1] == 'O': queue.append((i, n-1)) for j in range(n): if board[0][j] == 'O': queue.append((0, j)) if board[m-1][j] == 'O': queue.append((m-1, j)) # BFS标记所有连通区域 while queue: i, j = queue.popleft() if 0 <= i < m and 0 <= j < n and board[i][j] == 'O': board[i][j] = 'S' queue.append((i+1, j)) queue.append((i-1, j)) queue.append((i, j+1)) queue.append((i, j-1)) # 最终处理 for i in range(m): for j in range(n): if board[i][j] == 'O': board[i][j] = 'X' elif board[i][j] == 'S': board[i][j] = 'O'

4.2 复杂度分析

时间复杂度：O(M×N)，每个节点最多被访问两次（标记和最终处理）
空间复杂度：O(M×N)，最坏情况下需要存储所有边缘节点

5. 面试中的进阶考察点

5.1 如何应对面试官的追问

在实际面试中，面试官可能会提出以下进阶问题：

如果矩阵太大无法放入内存怎么办？
- 答：可以分块处理，但需要额外记录边缘信息
如何并行化这个算法？
- 答：可以按行/列分片，但需要处理边界处的'O'区域合并
如果'O'和'X'的含义反转（找被'O'包围的'X'）会怎样？
- 答：算法逻辑完全对称，只需调整标记条件

5.2 实际工程中的应用变种

这类"区域填充"算法在实际工程中有很多应用场景：

图像处理中的连通区域分析
地图服务中的封闭区域检测
游戏开发中的地形生成
电路设计中的短路检测

6. 代码模板与记忆技巧

6.1 通用DFS/BFS模板

对于矩阵类的DFS/BFS问题，可以记住这个通用模板：

def matrix_dfs_bfs(matrix): if not matrix: return m, n = len(matrix), len(matrix[0]) directions = [(1,0), (-1,0), (0,1), (0,-1)] # 四连通方向 # DFS递归实现 def dfs(i, j): # 边界检查 if not (0 <= i < m and 0 <= j < n): return # 业务逻辑判断 if matrix[i][j] != target_condition: return # 处理当前节点 process_current(matrix, i, j) # 递归邻居 for di, dj in directions: dfs(i+di, j+dj) # BFS队列实现 from collections import deque queue = deque(initial_nodes) while queue: i, j = queue.popleft() # 边界检查 if not (0 <= i < m and 0 <= j < n): continue # 业务逻辑判断 if matrix[i][j] != target_condition: continue # 处理当前节点 process_current(matrix, i, j) # 加入邻居 for di, dj in directions: queue.append((i+di, j+dj))