1. 从一道被标记为“中等”的题说起力扣第130题“被围绕的区域”英文原名Surrounded Regions在力扣题库里被归类为中等难度。很多刷题的朋友第一次看到这道题脑子里冒出来的第一个念头是“这不就是个找连通块的问题吗”然后动手写了一个DFS结果提交之后发现要么栈溢出要么答案不对。我自己第一次做这道题的时候也踩了不少坑所以今天借着每日打卡Day16的机会把这道题从头到尾拆一遍把里面涉及的核心思路、实现细节、常见陷阱都讲清楚。这道题的核心场景是这样的给你一个二维矩阵里面只有两种字符X和O。要求你把所有被X完全包围的O翻转成X而那些在边界上或者与边界上的O相连的O则保持不变。听起来很简单但真正动手写的时候判断“被围绕”这个条件并不像想象中那么直观。这道题适合谁看如果你正在刷力扣、准备面试、或者想系统学习图论中的连通性问题这道题是一个非常好的练习素材。它同时涉及深度优先搜索、广度优先搜索、并查集三种解法而且每种解法都有不同的思维角度。更重要的是这道题教会我们一个非常重要的解题技巧正难则反。与其去判断哪些O被包围了不如反过来判断哪些O没有被包围。这个思路转换是整道题的精髓所在。接下来的内容我会从题目分析、思路拆解、三种解法的完整实现、常见问题排查、以及面试中的变体拓展几个维度来展开尽量把每一个细节都讲透让你看完之后不仅能AC这道题还能把类似的连通块问题一并拿下。2. 题目深度解析与核心难点拆解2.1 题目规则的精确定义先把题目规则用最直白的话说一遍。给定一个m行n列的二维字符矩阵board矩阵中的每个元素要么是X要么是O。你需要找到所有被X完全包围的连通O区域把这些区域里的O全部替换成X。这里有几个关键词需要特别注意。“完全包围”意味着这个O所在的连通块不能触及矩阵的任何一条边界。换句话说如果一个O位于矩阵的第一行、最后一行、第一列或者最后一列那它一定不会被翻转。同样如果一个O虽然不在边界上但它通过上下左右四个方向注意只有四个方向不含对角线能连通到边界上的某个O那它也不会被翻转。“连通”的定义是四方向连通也就是上下左右。这一点非常重要因为有些题目会考虑八方向连通包含对角线但这道题明确只有四方向。如果你不小心写成了八方向在某些测试用例上会得到错误答案。2.2 为什么直接判断“被围绕”很困难很多人第一反应是遍历整个矩阵对每个O判断它是否被X包围。但这个判断本身就是一个递归问题你要判断一个O是否被包围就需要判断它连通的所有O是否都被包围而这些O又需要判断它们连通的O……这就形成了一个循环依赖。更麻烦的是你无法通过局部信息来判断一个O是否被包围。比如下面这个矩阵X X X X X O O X X X O X X O X X位于(1,1)的O看起来被X包围了但它连通到(1,2)的O再连通到(2,2)的O而(2,2)的O又连通到(3,1)的O——这个O在最后一列吗不在。但它在最后一行吗(3,1)是第四行第一列它在最后一行上。所以整个连通块都不会被翻转。如果你从每个O出发去判断就需要先找到完整的连通块再判断这个连通块是否触及边界。这样做虽然可行但代码复杂度会高很多而且容易在递归过程中重复访问已经处理过的节点。2.3 逆向思维从边界出发标记“安全区域”这道题最优的解法思路是反过来想哪些O是安全的答案很明确——所有与边界上的O直接或间接连通的O都是安全的。剩下的O就是被包围的需要翻转。所以算法可以分成三步遍历矩阵的四条边界对每条边界上的每个O用DFS或BFS标记所有与它连通的O把这些O暂时改成另一个字符比如#或S表示“已确认安全”。遍历整个矩阵把没有被标记的O改成X这些就是被包围的。把标记为#的字符改回O。这个思路的美妙之处在于你不需要去判断“是否被包围”只需要从边界出发做一次连通性搜索剩下的自然就是被包围的。这就是典型的“正难则反”思想。2.4 三种解法的适用场景对比这道题有三种主流解法DFS、BFS和并查集。每种解法各有优劣我整理了一个对比表格解法时间复杂度空间复杂度优点缺点DFSO(mn)O(mn)最坏情况代码简洁思路直观递归深度可能过大导致栈溢出BFSO(mn)O(mn)不会栈溢出适合大规模数据代码稍长需要维护队列并查集O(mn·α)O(mn)思路独特适合处理动态连通性实现复杂常数较大对于这道题来说如果矩阵规模不大比如m和n都在200以内DFS是最简洁的选择。但如果矩阵规模很大比如1000×1000DFS的递归深度可能达到10^6级别这时候就必须用BFS或者手动模拟栈来避免栈溢出。并查集虽然也能做但在这道题里并没有明显优势反而代码量更大一般面试中不推荐作为首选。提示力扣的测试用例中矩阵最大规模是200×200所以用DFS在大多数语言中都不会栈溢出。但如果你在面试中遇到这道题面试官可能会追问“如果矩阵很大怎么办”这时候你需要能说出BFS或迭代式DFS的方案。3. 深度优先搜索解法最直观的入门方案3.1 DFS的核心逻辑与代码框架DFS解法的核心逻辑非常直接从边界上的每个O出发向四个方向递归搜索把所有连通的O标记为安全。代码框架大致如下class Solution: def solve(self, board): if not board or not board[0]: return m, n len(board), len(board[0]) def dfs(i, j): if i 0 or i m or j 0 or j n or board[i][j] ! O: return board[i][j] # dfs(i1, j) dfs(i-1, j) dfs(i, j1) dfs(i, j-1) # 从四条边界出发 for i in range(m): dfs(i, 0) dfs(i, n-1) for j in range(n): dfs(0, j) dfs(m-1, j) # 翻转被包围的O恢复安全的O for i in range(m): for j in range(n): if board[i][j] O: board[i][j] X elif board[i][j] #: board[i][j] O这段代码看起来很简单但里面有几个细节值得展开说。3.2 边界遍历的写法技巧注意上面代码中边界遍历的写法。我见过很多人的第一反应是写四个循环分别处理上、下、左、右四条边但这样容易漏掉角落的元素或者重复处理。更优雅的写法是用两个循环第一个循环遍历每一行分别处理第一列和最后一列的元素。第二个循环遍历每一列分别处理第一行和最后一行的元素。这样写的好处是角落元素会被处理两次但由于我们在dfs函数开头就检查了board[i][j] ! O第二次进入时会直接返回不会造成任何问题。而且这种写法比四个独立循环更不容易出错。还有一种写法是把所有边界坐标收集到一个列表里然后统一遍历。这种写法在BFS中更常见因为BFS需要把边界上的O先加入队列。3.3 递归终止条件的三个检查dfs函数的终止条件有三个检查顺序很重要坐标越界检查i 0 or i m or j 0 or j n字符检查board[i][j] ! O标记并递归为什么把越界检查放在最前面因为如果坐标越界了访问board[i][j]会直接报数组越界错误。所以必须先检查坐标合法性再检查字符内容。为什么用board[i][j] ! O而不是board[i][j] X因为我们在搜索过程中会把O改成#如果只检查X那么已经标记过的#会被重复访问导致无限递归。用! O可以同时排除X和#确保每个节点只被访问一次。3.4 递归深度与栈溢出的实际测试我在本地用Python测试过当矩阵规模为200×200且全部是O时DFS的最大递归深度大约是40000层因为每次递归会向一个方向深入最坏情况下是一条蛇形路径。Python默认的递归限制是1000层所以如果不调整递归限制会直接报RecursionError。解决办法有两种一是用sys.setrecursionlimit()把递归限制调大比如调到100000二是改用BFS或迭代式DFS。在力扣的提交环境中Python的递归限制通常已经被调整过所以直接提交DFS代码一般不会出问题。但如果你在本地跑测试用例记得手动调整递归限制。import sys sys.setrecursionlimit(100000)注意调整递归限制并不是万能的。如果递归深度真的到了10^6级别即使调整了限制也可能因为栈空间不足而崩溃。所以对于超大规模矩阵BFS是更稳妥的选择。4. 广度优先搜索解法更稳健的工程选择4.1 BFS的队列设计与实现BFS解法的思路和DFS完全一致只是把递归换成了队列。代码实现如下from collections import deque class Solution: def solve(self, board): if not board or not board[0]: 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)) board[i][0] # if board[i][n-1] O: queue.append((i, n-1)) board[i][n-1] # for j in range(n): if board[0][j] O: queue.append((0, j)) board[0][j] # if board[m-1][j] O: queue.append((m-1, j)) board[m-1][j] # # BFS搜索 directions [(1,0), (-1,0), (0,1), (0,-1)] while queue: i, j queue.popleft() for di, dj in directions: ni, nj i di, j dj if 0 ni m and 0 nj n and board[ni][nj] O: board[ni][nj] # queue.append((ni, nj)) # 最终翻转 for i in range(m): for j in range(n): if board[i][j] O: board[i][j] X elif board[i][j] #: board[i][j] O4.2 入队时标记 vs 出队时标记BFS中有一个非常关键的细节到底是在入队时标记已访问还是在出队时标记这两种写法都能得到正确答案但效率差别很大。如果在出队时才标记那么同一个节点可能被多次加入队列。比如节点A和节点B都连通到节点CA先入队B后入队当A出队时发现C是O把C入队当B出队时又发现C是O因为C还没被标记又把C入队一次。这样队列中会出现大量重复元素最坏情况下时间复杂度会退化。正确的做法是在入队时就立即标记。上面代码中每次把坐标加入队列之前都先把board[ni][nj]改成#这样后续的其他节点就不会再把它加入队列了。这个细节在面试中经常被考察很多人写BFS时容易忽略。4.3 BFS的空间复杂度分析BFS的空间复杂度主要取决于队列的最大长度。在最坏情况下比如整个矩阵都是O队列中同时存在的元素数量可能达到O(mn)级别。但实际上由于我们在入队时就标记了已访问队列中的元素不会重复所以队列的最大长度不会超过矩阵中O的总数。相比之下DFS的空间复杂度取决于递归深度最坏情况下也是O(mn)。所以在空间复杂度上BFS和DFS没有本质区别。但BFS的优势在于不会栈溢出因为队列是分配在堆上的不受调用栈大小限制。4.4 方向数组的写法与优化上面代码中用了directions数组来遍历四个方向这是BFS和DFS中常见的写法。但有些朋友可能会觉得用数组遍历有额外的循环开销所以选择手动写四次判断。两种写法在性能上的差异微乎其微但在代码可读性上方向数组明显更好。如果你追求极致性能可以把方向数组写成元组而不是列表因为元组的访问速度略快于列表。另外把directions定义在循环外面而不是每次BFS时重新创建也能节省一点点开销。不过这些优化在力扣的测试规模下基本看不出来更多是代码风格问题。5. 并查集解法另一种视角的连通性问题5.1 并查集的核心思想与适用场景并查集Union-Find是处理连通性问题的经典数据结构。在这道题中我们可以把所有边界上的O以及它们连通的O合并到同一个集合中然后遍历整个矩阵把不在这个集合中的O翻转成X。具体做法是虚拟一个“边界节点”把所有边界上的O都与这个虚拟节点合并。然后遍历矩阵中所有的O如果它上下左右有O就把它们合并。最后再遍历一次矩阵如果某个O与虚拟节点不在同一个集合中就翻转成X。5.2 并查集的实现细节class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 def connected(self, x, y): return self.find(x) self.find(y) class Solution: def solve(self, board): if not board or not board[0]: return m, n len(board), len(board[0]) dummy m * n # 虚拟边界节点 uf UnionFind(m * n 1) def index(i, j): return i * n j # 合并边界上的O与虚拟节点 for i in range(m): for j in range(n): if board[i][j] O: if i 0 or i m-1 or j 0 or j n-1: uf.union(index(i, j), dummy) else: # 与上下左右的O合并 if board[i-1][j] O: uf.union(index(i, j), index(i-1, j)) if board[i1][j] O: uf.union(index(i, j), index(i1, j)) if board[i][j-1] O: uf.union(index(i, j), index(i, j-1)) if board[i][j1] O: uf.union(index(i, j), index(i, j1)) # 翻转不与虚拟节点连通的O for i in range(m): for j in range(n): if board[i][j] O and not uf.connected(index(i, j), dummy): board[i][j] X5.3 并查集解法的性能分析并查集的时间复杂度是O(mn·α(mn))其中α是阿克曼函数的反函数在实际应用中可以认为是常数。所以并查集的时间复杂度和DFS/BFS一样都是O(mn)。但并查集的常数因子更大因为每次union和find操作都涉及路径压缩和按秩合并。在这道题中并查集的代码量明显大于DFS和BFS而且需要额外维护parent和rank数组空间开销也更大。所以除非题目有特殊要求比如需要动态添加连通关系否则不推荐用并查集做这道题。不过学习并查集解法仍然有价值因为它提供了一种不同的思维角度把连通性问题转化为集合合并问题。这种思维方式在处理更复杂的图论问题时非常有用。6. 常见问题排查与避坑指南6.1 为什么我的DFS会栈溢出这是新手最常遇到的问题。前面已经分析过当矩阵规模较大且存在长路径时DFS的递归深度可能超过语言默认的递归限制。解决办法有三种调整递归限制Python中用sys.setrecursionlimit改用BFS用显式栈模拟递归第三种方法虽然代码复杂一些但最稳妥。下面是一个用显式栈实现的迭代式DFSdef solve(self, board): if not board or not board[0]: return m, n len(board), len(board[0]) stack [] for i in range(m): for j in range(n): if board[i][j] O and (i 0 or i m-1 or j 0 or j n-1): stack.append((i, j)) board[i][j] # while stack: i, j stack.pop() for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]: ni, nj i di, j dj if 0 ni m and 0 nj n and board[ni][nj] O: board[ni][nj] # stack.append((ni, nj)) for i in range(m): for j in range(n): if board[i][j] O: board[i][j] X elif board[i][j] #: board[i][j] O6.2 边界遍历遗漏角落元素很多人在写边界遍历时会写成四个独立的循环for j in range(n): dfs(0, j) # 第一行 for j in range(n): dfs(m-1, j) # 最后一行 for i in range(m): dfs(i, 0) # 第一列 for i in range(m): dfs(i, n-1) # 最后一列这种写法本身没有问题但如果你不小心把某个循环的范围写错了比如把range(n)写成了range(1, n-1)就会遗漏边界上的元素。更隐蔽的错误是把四个循环的顺序搞混导致某些角落元素被跳过。我推荐用前面提到的两循环写法或者把所有边界坐标收集到一个列表中统一处理。后者在BFS中更常见因为BFS需要先把边界上的O加入队列。6.3 标记字符的选择与恢复在标记安全区域时我们需要选择一个临时字符来替换O。这个字符不能是X因为最后我们要把未标记的O改成X如果临时字符也是X就无法区分了。常见的选择有#、S、A等。选择临时字符时要注意这个字符不能与矩阵中已有的字符冲突。题目中矩阵只包含X和O所以任何其他字符都可以。但如果你在面试中遇到变体题目矩阵中可能包含其他字符这时候需要选择一个绝对不会出现的字符。恢复阶段就是把临时字符改回O把剩余的O改成X。这个阶段的顺序很重要必须先处理O再处理临时字符或者用if-elif结构确保每个元素只被处理一次。如果先恢复临时字符再翻转O那么恢复后的O会被误翻转成X。6.4 常见错误速查表错误现象可能原因解决方法栈溢出DFS递归深度过大改用BFS或调整递归限制答案错误部分O未翻转边界遍历遗漏检查四条边是否都遍历到答案错误部分O被误翻转标记字符与恢复逻辑冲突检查临时字符选择和恢复顺序无限递归未标记已访问节点在递归/入队时立即标记数组越界坐标检查顺序错误先检查坐标合法性再访问数组超时BFS出队时才标记改为入队时立即标记7. 面试中的变体与拓展思路7.1 变体一八方向连通如果题目改成八方向连通包含对角线解法基本不变只需要把方向数组从四个方向扩展到八个方向directions [(1,0), (-1,0), (0,1), (0,-1), (1,1), (1,-1), (-1,1), (-1,-1)]但要注意八方向连通会改变连通块的范围某些在四方向下被包围的O在八方向下可能就连通到边界了。所以测试用例的答案会完全不同。7.2 变体二翻转被包围的指定字符如果题目改成翻转被包围的A而不是O解法完全一样只需要把代码中所有的O替换成A即可。这种变体主要考察你是否真正理解了算法的本质而不是死记硬背代码。7.3 变体三求被包围区域的数量如果题目改成求被包围的连通块数量而不是翻转它们那么需要在DFS/BFS中额外维护一个计数器。每从一个未访问的O出发完成一次搜索计数器加一。但要注意只有被包围的连通块才计数所以需要先标记安全区域再统计剩余O的连通块数量。7.4 变体四动态添加障碍物如果题目允许在矩阵中动态添加X然后查询某个O是否被包围这就变成了一个动态连通性问题。这种情况下并查集是更好的选择因为并查集支持高效的合并操作而DFS/BFS每次查询都需要重新搜索。7.5 从这道题延伸出的通用解题模板这道题的核心思想可以总结为一个通用模板当需要判断“被包围”或“内部”元素时从边界出发标记“外部”元素剩下的就是“内部”元素。这个模板在很多题目中都有应用比如岛屿数量问题中从边界出发标记与边界连通的陆地迷宫问题中从入口出发标记可达区域图像处理中从边缘出发进行泛洪填充掌握这个模板你就能解决一大类连通性问题。8. 我的刷题心得与实战建议做这道题最大的收获不是学会了DFS或BFS的写法而是理解了“正难则反”的思维方式。很多时候直接求解一个问题很困难但反过来求解它的补集却很简单。这种思维转换在算法题中非常常见比如求“被包围的区域”很难但求“不被包围的区域”很简单求“满足条件的最小值”很难但判断“某个值是否满足条件”很简单二分答案求“有多少种方案”很难但求“总方案数减去不合法方案数”很简单容斥原理我在实际刷题中发现那些看起来难度较高的题目往往都有一个巧妙的思维转换点。找到这个转换点题目就会变得非常简单。而找到转换点的关键就是多问自己一句“如果反过来想呢”另外关于代码实现我建议大家在刷这道题时至少用两种方法各写一遍。DFS写一遍BFS写一遍感受一下两种搜索方式的区别。如果时间充裕再用并查集写一遍。三种方法都写过之后你对连通性问题的理解会上升一个层次。最后分享一个小技巧在写DFS时如果担心栈溢出可以先用小规模测试用例验证逻辑正确性然后再用大规模用例测试性能。力扣的测试用例通常包含边界情况比如空矩阵、单元素矩阵、全O矩阵、全X矩阵等。自己写测试时也要覆盖这些情况确保代码的鲁棒性。关于这道题后续还可以这样扩展你可以尝试把矩阵改成三维的判断三维空间中哪些O被X包围。解法和二维完全一样只是方向数组从四个变成六个。这种三维连通性问题在图像处理和游戏开发中很常见比如判断一个三维模型内部的空腔是否与外部连通。