算法精讲：反向BFS与虚拟边界技巧解决网格填涂颜色问题

1. 问题引入从“涂色”到“连通性”的思维跃迁很多朋友在初次接触编程竞赛或算法题时看到“填涂颜色”这类题目第一反应往往是“这不就是个简单的二维数组遍历和赋值吗” 比如题目描述一个由0和1组成的矩阵1代表边界或障碍要求将其中被1包围的0区域全部涂成2。乍一看这确实像是一个“画笔”工具找到一块0的区域然后把它涂满。但如果你真的用这种“看到0就涂色”的朴素深度优先搜索DFS或广度优先搜索BFS去实现十有八九会掉进坑里。这道题真正的核心远不止“涂色”这么简单它考察的是对连通性的深刻理解以及如何巧妙地处理边界条件。它本质上是一个“寻找被完全包围的连通区域”的问题是图论中“连通分量”概念在二维网格上的经典应用。我最初做这类题时就曾想当然地从矩阵内部的某个0点开始扩散涂色结果程序要么把不应该涂的边界连通区域也涂了要么在复杂形状面前束手无策。后来才明白正向“找内圈”的思路往往比反向“找外圈”的思路要复杂得多。这道“填涂颜色”题就是一个绝佳的训练场它能帮你彻底扭转思维定式掌握一种高效且鲁棒的“反向BFS/DFS 标记”的解题范式。这个范式不仅能解决这道题还能迁移到“岛屿数量”、“被围绕的区域”、“飞地的数量”等一系列经典问题上。接下来我就带你彻底拆解这个问题从最易错的思路讲起一步步推导出最优解并分享几个调试和优化的关键技巧。2. 常见陷阱与错误思路剖析在给出正确方案前我们先看看为什么直观的想法行不通。假设我们有一个 N x N 的网格grid[i][j] 1表示墙或边界0表示待判断区域。错误思路一从任意内部0点开始搜索并涂色这是最直觉的陷阱。算法步骤可能是遍历网格找到一个值为0的单元格。从这个0点启动DFS/BFS搜索所有与其相连的0点四方向。在搜索过程中将访问到的0点涂成2。遍历结束后输出网格。这个思路的问题在于你无法判断当前找到的这片0区域是否真的被1完全包围。例如矩阵边缘的0点它可能与矩阵外部视为被1包围不外部是无穷的0相连这片区域就不应该被涂色。但你的算法从它开始会错误地将这片连通到边界的区域也涂成2。换句话说你缺少一个机制来判断当前连通分量是否是“封闭”的。错误思路二先判断再涂色有人可能会改进在第一步搜索时同时检查搜索过程中是否会碰到网格边界。如果会碰到则说明该区域未被包围放弃涂色如果搜索完都没碰到边界则说明被包围进行二次遍历涂色。 这个思路逻辑上正确但实现起来非常繁琐且存在重复遍历。你需要为每一个尚未访问的0点区域都执行一次搜索来判断其属性时间复杂度在最坏情况下会很高接近O(N^4)。而且对于同一个被包围区域里面的每个0点都会被重复判断多次效率低下。错误思路三逐行逐列扫描的“射线法”想象一下用笔从网格外画线穿过根据交点奇偶性判断内外这在连续几何中如判断点是否在多边形内是常用方法但在离散的网格中边界情况点恰好在线上的处理极其复杂且不适用于需要标记整个区域的需求实现成本远高于图搜索。这些错误思路的根源都在于试图直接定位“内部”。在复杂的、不规则的“1”的包围圈面前直接判断一个点是否在内都困难何况要找出整个区域。我们需要一个更聪明、更“迂回”的策略。3. 核心解法反向BFS/DFS与“虚拟边界”技巧正确的解法核心是我们不直接寻找被包围的0区域而是先找出所有没有被包围的0区域即与外界连通的0区域并把它们标记出来。那么剩下的、未被标记的0区域自然就是被1包围的区域。如何找到所有与外界连通的0区域呢这里需要一个关键的思维转换将整个网格的“外部”视为一个特殊的、连通的“超级0区域”。任何与这个“超级外部区域”相连的网格内的0点都是不被包围的。具体操作上我们引入“虚拟边界”技巧在原始的 N x N 网格周围人工添加一圈“哨兵”单元格构成一个 (N2) x (N2) 的新网格。这一圈哨兵的值初始化为0代表“网格外部”。将原始网格的数据放入这个新网格的中央即从下标1到N的位置。从这个新网格的左上角(0,0)这是一个“外部”0点开始进行一次BFS或DFS。这次搜索的目标是遍历所有值为0且与这个“外部起点”连通的单元格。在搜索过程中将这些访问到的0点标记为另一个特殊值例如3表示“这些是连通到外部的0即不被包围的0”。搜索结束后我们遍历原始网格区域即新网格的[1, N]部分如果单元格的值是1保持为1边界。如果单元格的值是0说明它既不是1边界也没有在之前的搜索中被标记为3连通外部。那么它一定就是被1包围的0将其涂成2。如果单元格的值是3将其恢复为0或者直接输出0因为它是不被包围的0。这个方法的精妙之处在于化繁为简将难以定义的“外部”具体化为一圈可访问的0把“判断是否连通外部”这个全局问题转化为了一个标准的连通分量搜索问题。一次遍历全局搞定只需要从(0,0)开始进行一次搜索就能一次性标记出所有连通到外部的0区域。无需对每个疑似内部区域进行重复判断。鲁棒性强无论“1”围成的形状多么古怪无论被包围的0区域有多少个、在哪里这个方法都能正确处理。注意为什么选择(0,0)作为起点因为它一定在新添加的、代表外部的那个“0圈”上。从这个点开始搜索能确保访问到所有与外部相连的0。你也可以选择这一圈上的任意一个0点作为起点。4. 算法实现细节与代码逐行解析下面我们以广度优先搜索BFS为例给出详细的C实现。选择BFS是因为它使用队列在网格这类问题中通常比DFS的递归更直观且无栈溢出风险对于较大的网格。#include iostream #include queue #include vector using namespace std; int main() { int n; cin n; // 1. 创建带“虚拟边界”的网格大小为 (n2) x (n2) // 并将所有元素初始化为0代表外部和初始状态 vectorvectorint grid(n 2, vectorint(n 2, 0)); // 2. 读入原始数据填充到网格中心 [1, n] 的范围内 for (int i 1; i n; i) { for (int j 1; j n; j) { cin grid[i][j]; } } // 3. 定义方向数组上、下、左、右 int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 4. 从“外部”起点(0,0)开始BFS标记所有连通到外部的0 queuepairint, int q; q.push({0, 0}); grid[0][0] 3; // 标记为3表示“已访问且连通外部” while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (auto dir : dirs) { int nx x dir[0]; int ny y dir[1]; // 检查新坐标是否在扩展后的网格范围内 if (nx 0 nx n 2 ny 0 ny n 2) { // 如果邻居是0说明它和外部连通将其标记并入队 if (grid[nx][ny] 0) { grid[nx][ny] 3; q.push({nx, ny}); } } } } // 5. 根据标记结果输出最终答案 for (int i 1; i n; i) { for (int j 1; j n; j) { if (grid[i][j] 1) { cout 1 ; } else if (grid[i][j] 0) { // 内部的0未被步骤4标记到的就是要涂色的部分 cout 2 ; } else { // grid[i][j] 3 // 连通到外部的0恢复输出为0 cout 0 ; } } cout endl; } return 0; }关键点解析网格扩展 (第11行)vectorvectorint grid(n 2, vectorint(n 2, 0));这行代码创建了扩展网格。n2是关键上下左右各多出一圈。初始化值为0这很关键它保证了我们添加的边界本身就是“外部区域”的一部分。数据读入范围 (第14-18行)读入数据时索引从1开始到n结束正好对应原始网格在扩展网格中的位置。这是避免数组越界和逻辑错误的关键。BFS起点与标记 (第27-29行)我们从(0,0)开始并立即将其值从0改为3。这里的“3”是一个临时标记用于区分“普通的0”、“墙1”和“连通外部的0”。你也可以用其他不会冲突的数字比如-1。BFS条件判断 (第36-40行)if (grid[nx][ny] 0)这个条件确保了搜索只会在值为0的区域蔓延。它不会穿过值为1的墙。这正是我们想要的找出所有能从外部到达的0区域。最终输出逻辑 (第46-55行)这是算法的收获阶段。1原样输出。0注意这里的0是经过BFS搜索后仍然为0的单元格。这意味着在之前的搜索中它没有被访问到没被改成3。为什么没被访问到因为它被值为1的单元格完全包围BFS从外部无法到达它。所以它就是我们要涂色的目标输出2。3这是被BFS标记过的、连通外部的0。它们不是目标所以恢复输出为0。5. 从“填涂颜色”到通用模型解决一类问题掌握了上述“反向BFS虚拟边界”的方法你就掌握了一类问题的通用钥匙。让我们看看它如何应用到其他经典题目上这能极大加深你的理解。LeetCode 130. 被围绕的区域给你一个m x n的矩阵board由若干字符X和O组成。找到所有被X围绕的区域并将这些区域里所有的O用X填充。 解释被围绕的区间不会存在于边界上换句话说任何边界上的O都不会被填充为X。这道题几乎是“填涂颜色”的字母版。‘X’对应1‘O’对应0。解题步骤一模一样假想网格四周有一圈‘O’虚拟边界。从这圈‘O’实际可以从四个边上的‘O’开始BFS/DFS标记所有连通到边界的‘O’例如标记为‘#’。遍历整个网格遇到‘X’不变。遇到‘O’此时一定是未被标记的、被包围的将其改为‘X’。遇到‘#’标记的将其恢复为‘O’。LeetCode 1020. 飞地的数量给你一个大小为m x n的二进制矩阵grid其中0表示海洋1表示陆地。一次移动是指从一个陆地单元格移动到另一个相邻上、下、左、右的陆地单元格或跨过grid的边界。返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。这道题可以理解为计算被“海洋0”完全包围的“陆地1”的数量。我们依然可以用反向思维从网格边界上的所有“陆地1”单元格开始BFS/DFS标记所有能够到达边界的陆地。最后遍历整个网格统计那些值为1陆地且未被标记的单元格数量。它们就是“飞地”。LeetCode 1254. 统计封闭岛屿的数目二维矩阵grid由0土地和1水组成。封闭岛是一个完全由1包围左、上、右、下的区域即区域外圈的所有相邻单元格都是水。返回封闭岛屿的数目。这道题是“填涂颜色”的逆问题我们要数的是被水包围的“土地0”的区域数量。方法依旧从矩阵边界上的所有“土地0”开始BFS/DFS淹没标记所有连通到边界的土地因为它们不是封闭岛。然后遍历矩阵内部不含边界当遇到一个“土地0”时启动一次BFS/DFS淹没整个岛屿同时将岛屿计数1。因为此时还能遇到的0一定是在步骤1中未被触及的、被水完全包围的“封闭岛”。通过以上对比你会发现这些问题的本质都是在二维网格上寻找特定的连通分量而“反向搜索标记边界连通区域”是解决这类“内外判断”问题的标准范式。理解了这个范式你就能举一反三快速解决一系列相关问题。6. 性能分析与优化探讨我们实现的BFS解法时间复杂度和空间复杂度都是 O(M*N)其中M和N是网格的维度包括扩展的边界。这已经是此类问题最优的复杂度了因为我们必须访问每一个单元格至少一次。空间优化在上面的代码中我们使用了一个(n2) x (n2)的二维向量。对于某些内存限制极端严格的环境虽然本题一般不会我们可以尝试“原地修改”的优化但会牺牲一些代码清晰度。基本思路是先遍历网格的四条边对边上的每一个0启动DFS/BFS将其标记。这样就不需要显式扩展网格但需要在DFS/BFS函数中额外判断当前点是否在边界上i0 || in-1 || j0 || jn-1逻辑上稍微绕一点。我个人在竞赛和面试中更推荐第一种“虚拟边界”法因为它逻辑清晰不易出错多消耗的 O(N) 级空间在绝大多数情况下是可接受的。BFS vs DFSBFS队列通常使用显式队列无递归深度限制适合大规模网格。代码模板化程度高。DFS递归代码更简洁但存在栈溢出风险网格很大且连通区域很大时。对于竞赛和算法题如果网格边长N在100~200量级递归DFS通常没问题如果达到500甚至1000稳妥起见建议用BFS。一个实用的调试技巧当你对算法的中间状态不确定时可以在BFS标记完成后、最终输出前先打印出整个扩展网格的状态。这样你可以清晰地看到哪些0被标记成了3连通外部。哪些0还保持为0即将被涂色。1的墙是否完好无损。 这能帮你快速定位逻辑错误。例如如果你发现某块明明应该被涂色的内部0区域也被标记成了3那很可能是你的方向数组写错了或者BFS的边界条件判断有误导致搜索“穿墙”了。7. 举一反三变种问题与思维拓展掌握了基础模型后我们可以思考一些变种这能锻炼你灵活运用算法思想的能力。变种1如果1不是墙而是另一种颜色要求涂色的是被1包围的0区域但1本身不一定是连续的围墙可能是一个闭合的环我们的算法依然有效因为算法并不关心“1”是否连成一个圈。它只关心两件事BFS从外部开始遇到1就停止扩散。最终剩下的0就是所有无法从外部到达的0。 即使1是断断续续的但只要它们整体上构成了一个“封闭”的屏障使得内部的0无法与外部连通那么这些0就会被正确识别。算法的正确性依赖于连通性的定义而不是“墙”的形状。变种2要求输出被包围区域的个数而不仅仅是涂色。这就像LeetCode 1254。在现有算法基础上当我们在最后遍历到内部0时不要只是简单地输出2而是以这个0为起点再进行一次BFS/DFS把整个被包围区域遍历一遍同时涂色或标记为已访问并将计数器加1。这样在输出涂色结果的同时也能得到区域数量。变种3网格从正方形变为矩形或者从四方向连通变为八方向连通。矩形我们的算法完全通用只需将扩展网格的大小从(n2)改为(m2) x (n2)即可。八方向包括对角线这改变了连通性的定义。你只需要修改方向数组dirs从4个方向增加到8个方向{ {-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1} }。算法的其他部分完全不变。这体现了算法框架的灵活性。思维拓展为什么这是“染色法”或“洪水填充”的典型应用“洪水填充”形象地描述了从一点开始像水蔓延一样覆盖连通区域的过程。本题中我们做了两次“洪水填充”第一次填充外部洪水从虚拟边界“放水”水会流经所有与外部连通的0区域并将它们“染”成颜色3。第二次识别内部旱地所有没有被第一次洪水染到色的0区域就是干燥的、被1堤坝围起来的“洼地”也就是我们要涂色的目标。 这种“正难则反”、“从外部包围内部”的思想在解决很多搜索和标记问题时都非常有效。