1. 问题引入从棋盘游戏到矩阵搜索最近在整理算法笔记时翻到了一个挺有意思的题目题目名字叫“被围绕的区域”。乍一看这名字有点抽象但如果你把它想象成一个棋盘游戏或者一个简单的图像处理问题就很好理解了。想象一下你有一个二维的棋盘上面有两种棋子一种是“O”一种是“X”。现在游戏规则是所有被“X”棋子完全包围上下左右四个方向的“O”棋子都要被翻转成“X”。但是如果“O”棋子位于棋盘的边缘或者通过上下左右移动能够连接到棋盘边缘的“O”那么这些“O”就是“幸存者”不能被翻转。这其实就是LeetCode上第130题“被围绕的区域”所描述的场景。题目会给你一个m x n的字符矩阵board其中‘X’和‘O’。你需要实现一个函数将所有被‘X’围绕的‘O’都替换为‘X’。而那些与边界相连的‘O’则保持不变。为什么这个问题值得拿出来单独讲因为在很多涉及矩阵搜索、图像连通域分析、甚至是游戏地图处理的场景里这种“从边界向内渗透”的思想非常关键。它不仅仅是简单的深度优先搜索DFS或广度优先搜索BFS遍历更包含了一种“逆向思维”与其费力地去寻找所有被包围的内部区域不如先标记出所有不可能被包围的“安全区”剩下的自然就是需要处理的目标了。这种思路能极大地简化问题也是这道题的核心考点。2. 核心思路拆解为什么是“从外向内”的DFS当我们拿到一个矩阵最直观的想法可能是遍历整个矩阵遇到一个‘O’就看看它是否被‘X’完全包围。但这个“判断是否被包围”的操作非常复杂。你需要以这个‘O’为起点进行搜索检查它的连通区域是否接触到了矩阵边界。如果接触到了那整个连通区域都是安全的如果没接触到那整个连通区域都需要被翻转。这个过程中你可能会对同一个‘O’区域进行重复的搜索和判断效率很低。一个更高效、更聪明的策略是“从边界出发标记所有安全区域”。具体步骤如下边界扫描我们首先遍历矩阵的四条边第一行、最后一行、第一列、最后一列。只要在边界上发现‘O’这个‘O’以及所有与它相连的‘O’就一定是“安全”的因为它们直接或间接地接触到了边界不可能被完全包围。标记安全区对于每一个边界上的‘O’我们以其为起点进行一次深度优先搜索DFS或广度优先搜索BFS将所有与之连通的‘O’都标记为一个特殊的临时值例如‘#’。这个标记的意思是“此位置是‘O’但它是安全的最终需要保留。”全局清理与替换完成所有边界出发的搜索和标记后我们再次遍历整个矩阵。此时所有未被标记的‘O’即那些没有被‘#’覆盖的‘O’就是被‘X’完全包围的内部区域我们将它们替换成‘X’。同时我们把之前标记的所有‘#’恢复成‘O’。这样安全的‘O’区域就保留了下来。这个思路的精妙之处在于它把原本需要针对每个内部区域进行复杂判断的问题转化为了两次简单的矩阵遍历和一次从边界出发的连通区域标记。时间复杂度从可能的高阶降到了稳定的O(m*n)因为每个单元格最多被访问常数次。2.1 深度优先搜索DFS的实现要点既然题目提示了用DFS我们就重点聊聊DFS的实现。DFS的本质是“一条路走到黑走不通再回头”非常适合用来探索一个连通区域。在这个问题里DFS函数dfs(int i, int j)的职责很明确如果当前位置(i, j)是有效的矩阵坐标并且该位置的值是‘O’那么我们就将其标记为‘#’然后递归地向其四个方向上、下、左、右继续探索。这里有几个关键的实现细节和容易踩坑的地方递归的终止条件这是DFS不写崩的基础。条件必须包括坐标越界i 0 || j 0 || i m || j n。当前位置不是‘O’可能是‘X’或已经被标记过的‘#’。方向数组的使用定义一个二维数组int[][] dirs {{1,0}, {-1,0}, {0,1}, {0,-1}};来代表四个方向的偏移量。这样在递归时代码会更清晰避免写四行相似的递归调用。避免递归栈溢出虽然题目常见的矩阵尺寸比如200x200下递归深度一般不会导致栈溢出但这是一个好习惯。对于特别大的矩阵递归DFS可能会导致StackOverflowError。在这种情况下可以改用显式栈Stack进行迭代式的深度优先搜索或者直接使用BFS队列实现。BFS在空间消耗上通常更稳定但DFS的代码通常更简洁。作为一道算法题递归DFS通常是可接受的。注意在标记边界‘O’时我们只对边界上的点发起DFS调用。千万不要在标记阶段去遍历整个矩阵然后调用DFS那会做大量无用功又退化成了最初的笨办法。3. 代码实现与逐行解析理解了思路我们来看具体的Java代码实现。我会把代码分成几个部分并加上详细的注释。class Solution { // 方向数组分别代表下、上、右、左 int[][] dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int m, n; // 矩阵的行数和列数 public void solve(char[][] board) { if (board null || board.length 0) return; m board.length; n board[0].length; // 步骤1遍历四条边对边界上的‘O’进行DFS标记 // 第一列和最后一列 for (int i 0; i m; i) { if (board[i][0] O) dfs(board, i, 0); if (board[i][n - 1] O) dfs(board, i, n - 1); } // 第一行和最后一行 (注意角点已经被上面的循环处理过但重复判断无害) for (int j 0; j n; j) { if (board[0][j] O) dfs(board, 0, j); if (board[m - 1][j] O) dfs(board, m - 1, j); } // 步骤2遍历整个矩阵进行最终替换 for (int i 0; i m; i) { for (int j 0; j n; j) { if (board[i][j] O) { // 未被标记的‘O’是被包围的替换为‘X’ board[i][j] X; } else if (board[i][j] #) { // 被标记为安全区域的‘#’恢复为‘O’ board[i][j] O; } // 已经是‘X’的位置不变 } } } // DFS递归函数用于标记所有与(i,j)连通的‘O’ private void dfs(char[][] board, int i, int j) { // 递归终止条件越界或当前位置不是‘O’ if (i 0 || i m || j 0 || j n || board[i][j] ! O) { return; } // 将当前‘O’标记为特殊字符‘#’表示已访问且是安全区域 board[i][j] #; // 向四个方向递归探索 for (int[] dir : dirs) { int newI i dir[0]; int newJ j dir[1]; dfs(board, newI, newJ); } } }代码关键点解析边界遍历的顺序代码先遍历左右两列第一列和最后一列再遍历上下两行第一行和最后一行。顺序其实无所谓只要确保四条边上的每个点都被检查到即可。角上的点如(0,0)会被检查两次但这只是多了一次条件判断dfs函数内部的board[i][j] ! ‘O’会阻止重复递归所以没有副作用。标记字符的选择我们选择‘#’作为临时标记。这里必须选择一个原矩阵中不存在的字符。绝对不能标记为‘X’否则在后续DFS中这个“假X”会阻挡搜索导致连通区域标记不全。也不能标记为‘O’以外的其他字母以免混淆。最终替换的逻辑最后的双重循环是精髓。它同时完成了两件事if (board[i][j] ‘O’)经过前面的标记如果还有字符是‘O’说明它既不在边界也没有被任何从边界开始的DFS访问到那它一定是被包围的翻转为‘X’。else if (board[i][j] ‘#’)将我们之前标记的安全区域恢复为‘O’。 这个逻辑清晰地将矩阵分成了三类区域进行处理。4. 从DFS到BFS另一种实现视角虽然题目要求用DFS但了解BFS的实现同样重要尤其是在面对深度很大的图时BFS使用队列可以避免递归栈溢出的风险。思路完全一样只是把递归调用换成了队列操作。下面是使用BFS队列实现的bfs标记函数private void bfs(char[][] board, int i, int j) { if (board[i][j] ! O) return; Queueint[] queue new LinkedList(); queue.offer(new int[]{i, j}); board[i][j] #; // 入队即标记防止重复入队 while (!queue.isEmpty()) { int[] cell queue.poll(); int x cell[0], y cell[1]; // 遍历四个方向 for (int[] dir : dirs) { int newX x dir[0]; int newY y dir[1]; // 检查新坐标是否有效且为‘O’ if (newX 0 newX m newY 0 newY n board[newX][newY] O) { board[newX][newY] #; // 标记 queue.offer(new int[]{newX, newY}); // 入队 } } } }在主函数solve中只需要把调用dfs(board, i, j)的地方换成bfs(board, i, j)即可。DFS与BFS的选择DFS递归代码简洁直观易于理解。但在极端情况下如矩阵非常大且全是‘O’递归深度可能达到m*n有栈溢出风险。BFS队列使用显式的队列数据结构没有递归深度限制空间复杂度在最坏情况下也是O(m*n)。代码稍长但更稳健。对于算法面试通常说明思路并给出DFS版本即可。如果被问到优化或大数据处理可以再提出BFS版本作为改进。5. 实战中的陷阱与边界条件处理理论很完美但一写代码就出bug是算法练习中的常态。下面我总结几个在实现“被围绕的区域”时最容易栽跟头的地方。5.1 空输入与极小输入这是许多问题的“第零个”测试用例。我们的代码必须能处理。board为null。board为空数组[]。board为[[]]即只有一行但该行为空。 在代码开头我们必须加上防御性判断if (board null || board.length 0) return;。获取列数n时也要确保m0否则board[0].length会出错。上面的代码通过先判断board.length再赋值m自然规避了这个问题。5.2 标记字符的冲突前面提到过一定要用一个矩阵中绝对不可能出现的字符来做临时标记。除了‘#’也可以用其他字符如‘A’、‘*’等。但千万不要用‘X’或‘O’。我曾见过有人图省事想把安全的‘O’直接改成‘X’最后再改回来这会导致DFS搜索时刚被改成‘X’的点阻挡了对其相邻‘O’的继续探索造成标记不完全。5.3 递归函数中的重复访问与栈溢出在DFS函数中必须先标记再递归。顺序不能错。// 正确顺序 board[i][j] ‘#’; // 先标记 for (dir : dirs) { dfs(newI, newJ); // 再递归 } // 错误示范如果后标记在递归调用中可能会因为再次访问到自身通过邻居的邻居而导致无限递归或重复处理。 for (dir : dirs) { dfs(newI, newJ); // 先递归 } board[i][j] ‘#’;同时递归的终止条件board[i][j] ! ‘O’也包含了board[i][j] ‘#’的情况这防止了对已标记点的重复访问也构成了递归结束的重要条件。对于可能的大数据要在心里有根弦DFS递归可能溢出。虽然力扣的测试用例通常不会卡这个但知道BFS是更安全的备选方案是一个加分项。5.4 矩阵只有一行或一列的情况这是一个非常狡猾的边界条件。考虑一个1 x n的矩阵只有一行或者一个m x 1的矩阵只有一列。对于1 x n的矩阵它的“第一行”就是“最后一行”也是“唯一一行”。按照我们的算法我们会遍历这一行的所有列即所有元素因为它们都在边界上。所以这一行所有的‘O’都会被标记为安全最后都不会被翻转为‘X’。这是符合题意的因为在一行矩阵里所有元素都在边界不存在“被围绕”的概念。同理对于m x 1的矩阵所有元素都在第一列/最后一列也都是安全的。 我们的代码逻辑天然正确处理了这种情况不需要额外判断。6. 算法变种与扩展思考掌握了基础解法我们可以看看这个模式能解决哪些类似问题以及有哪些可以深入思考的方向。6.1 连通分量计数问题“被围绕的区域”本质是寻找与边界相连的连通分量。一个很自然的扩展是如何统计矩阵中‘O’形成的连通区域总数或者如何统计完全被‘X’包围的连通区域的数量总数遍历矩阵对每个未访问过的‘O’发起DFS/BFS标记整个连通区域计数器加一。被包围的数量可以先使用本题的“边界标记法”标记出所有安全区域。然后再次遍历矩阵对剩余的、未被标记的‘O’区域进行DFS/BFS并计数。这个数量就是被包围的区域数量。6.2 “岛屿”类问题的通用解法本题是“岛屿”系列问题的一个变种。经典的“岛屿数量”LeetCode 200问题是统计由‘1’陆地构成的连通区域数量其DFS/BFS的框架和本题一模一样只是没有了“从边界出发”这个前置条件而是需要全局搜索。这类问题的代码框架具有很强的复用性定义方向数组。编写一个dfs/bfs函数用于标记或处理一个连通分量。在主函数中以特定的顺序全局遍历或只遍历边界调用这个搜索函数。6.3 性能分析与优化我们的算法时间复杂度是O(m*n)因为每个单元格最多被访问两次一次标记一次最终替换。空间复杂度方面DFS递归取决于递归深度最坏O(m*n)。BFS队列同样最坏O(m*n)。标记本身是原地修改没有使用额外空间存储矩阵。这已经是理论上的最优复杂度了因为我们必须访问每个单元格至少一次。在实际面试中能清晰分析出这个复杂度即可。一个可能的“优化”讨论点在于我们是否真的需要遍历四条边对于某些形状的矩阵也许可以稍微减少几次循环。但在我看来这种优化带来的代码复杂性提升远大于其微乎其微的性能收益保持代码清晰易懂更重要。7. 测试用例设计与调试技巧自己写代码自己设计测试用例验证是提升算法能力的关键一步。对于本题我们可以设计以下几类测试用例常规用例// 输入 [[X,X,X,X], [X,O,O,X], [X,X,O,X], [X,O,X,X]] // 期望输出中间的那个‘O’被包围应翻转。右下角的‘O’在边界保留。 [[X,X,X,X], [X,X,X,X], [X,X,X,X], [X,O,X,X]]全为‘X’或全为‘O’全‘X’矩阵应无任何变化。全‘O’所有‘O’都在边界或与边界相连因此全部保留矩阵不变。边界情况单行单列[[O,X,O]]- 所有‘O’保留。空输入[]或null程序应正常返回不抛出异常。复杂连通// 一个巨大的‘O’区域中间包含‘X’但整体连接到边界。 // 这种用例用来测试DFS/BFS的标记是否能覆盖整个复杂区域。调试技巧 当程序输出不对时不要急于看代码。可以打印中间状态在完成边界标记后打印一下矩阵看看‘#’是否正确地标记了所有应该安全的‘O’区域。单步跟踪用一个简单的2x2或3x3矩阵在纸上手动模拟DFS的递归过程检查标记顺序和终止条件。检查循环边界确认遍历四条边的循环下标是否正确特别是m-1和n-1的使用。检查方向数组确保dirs数组包含了所有四个方向没有遗漏或重复。这道“被围绕的区域”是一个练习矩阵搜索和逆向思维的绝佳题目。它教会我们的不仅仅是DFS/BFS的写法更是一种“正难则反”的解题策略——当直接求解目标困难时尝试去标记它的补集非目标往往能豁然开朗。下次当你遇到类似“寻找内部封闭区域”的问题时不妨先想想能不能从边界开始