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(i1, j) dfs(i-1, j) dfs(i, j1) 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→恢复为O3.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(i1, j) dfs(i-1, j) dfs(i, j1) 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] O4. 工程优化用迭代代替递归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((i1, j)) queue.append((i-1, j)) queue.append((i, j1)) 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] O4.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(idi, jdj) # 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((idi, jdj))6.2 解题思路记忆口诀对于这类区域填充问题可以记住这个口诀 边缘入手标记活中间剩余全消灭解释先从边缘找到所有存活点与边缘连通的O标记这些存活点如改为S最后遍历整个矩阵未被标记的O→消灭改为X被标记的S→恢复改回O7. 同类问题举一反三掌握这个思路后可以轻松解决以下类似问题力扣200. 岛屿数量力扣695. 岛屿的最大面积力扣463. 岛屿的周长力扣529. 扫雷游戏力扣994. 腐烂的橘子这些问题的共同特点是都需要在矩阵中找到符合条件的连通区域只是处理逻辑稍有不同。建议按这个顺序练习逐步掌握变种问题的解法。
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(i1, j) dfs(i-1, j) dfs(i, j1) 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→恢复为O3.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(i1, j) dfs(i-1, j) dfs(i, j1) 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] O4. 工程优化用迭代代替递归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((i1, j)) queue.append((i-1, j)) queue.append((i, j1)) 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] O4.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(idi, jdj) # 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((idi, jdj))6.2 解题思路记忆口诀对于这类区域填充问题可以记住这个口诀 边缘入手标记活中间剩余全消灭解释先从边缘找到所有存活点与边缘连通的O标记这些存活点如改为S最后遍历整个矩阵未被标记的O→消灭改为X被标记的S→恢复改回O7. 同类问题举一反三掌握这个思路后可以轻松解决以下类似问题力扣200. 岛屿数量力扣695. 岛屿的最大面积力扣463. 岛屿的周长力扣529. 扫雷游戏力扣994. 腐烂的橘子这些问题的共同特点是都需要在矩阵中找到符合条件的连通区域只是处理逻辑稍有不同。建议按这个顺序练习逐步掌握变种问题的解法。
