C系列第15篇来聊聊BFS和FloodFill的组合。FloodFill的中文名挺形象洪水填充刷LeetCode或者打比赛的人应该都不陌生——岛屿数量、图像渲染、扫雷展开、被围绕的区域这些题全是它的马甲。面试时它出现频率也不低实现代码量不大却能同时考察队列、二维坐标处理、边界判断、循环终止条件这些基本功是面试官很喜欢用来快速摸底的一类题。这篇文章会把BFS_FloodFill拆成三层讲第一层是思路告诉你为什么这类问题天然该用BFS第二层是代码给出一套C模板可以直接套第三层是经验把常见的坑和调试方法整理出来。适合刚开始刷算法题的C学习者也适合准备算法面试想要快速复习一遍的人。1. 先搞清楚FloodFill到底在解决什么问题1.1 从一个格子扩散到整片连通区域FloodFill直译过来就是洪水填充想象你往一块地形图上的某个格子倒水水会沿着四周能渗透的地方慢慢流过去凡是流到的地方都算这片水域。算法要做的就是模拟这个“淹”的过程。更准确地说FloodFill处理的是这样一个问题给定一个二维矩阵或者说二维网格从一个起点格子出发把所有和它相邻、并且满足某个条件的格子全部标记出来。这里的“相邻”通常是上下左右四个方向也就是四邻域有些题目会要求八个方向也就是八邻域。“条件”最常见的是颜色相同、数值相等、或者是地图上的同一种可通行地形。生活里最典型的例子是画图软件的油漆桶你点一个封闭区域整个区域就被填充成新颜色。技术里的应用也很多扫雷里点到空白格会哗啦一下展开一片地图上统计连通水域或者陆地面积医疗影像里把连通的器官区域标记出来无人机把可行走区域自动圈出来背后都是同一套FloodFill逻辑。理解了问题本质就会发现FloodFill的关键词只有两个连通性和条件。只要二维矩阵里有一片满足相同条件的格子彼此相邻FloodFill就能把它们一次找全。这也是为什么它经常和“连通块”“区域标记”这类词同时出现在题目里——本质上都是在做同一个事情找连通块。1.2 为什么这题选BFS而不是DFSFloodFill并不一定非要BFSDFS同样能做两者都能把整个连通块完整遍历一遍。但我个人在C刷题和面试中绝大多数场景会优先选BFS理由可以摆成三点。第一点是栈空间安全。DFS如果写成递归每深入一层就要占用一层调用栈。C默认栈空间在Windows下通常是1MB左右Linux下通常是8MB听起来不小但在一个2000行2000列的网格里最坏情况递归深度接近400万层栈几乎秒炸。BFS用std::queue存节点内存分配在堆上只要堆够大就不会因为递归深度出事空间复杂度和DFS一样是O(R*C)但风险完全不同。第二点是扩展顺序可控。BFS天然按“圈层”向外扩散起点是第一层起点的邻居是第二层邻居的邻居是第三层……这种分层顺序在求最短步数、最少操作次数时特别有用第一次搜索到目标点时的层数就是最短距离。DFS则是一头扎到某个分支的深处再回头没法保证第一次碰到目标就是最优。第三点是代码结构固定、调试友好。BFS就是“队列 循环 方向数组”三件套没有递归边界这种容易漏的东西。哪怕不小心写错了打印队列内容也比追踪递归栈清晰得多。对于以“快速、稳定写出正确代码”为目标的面试和竞赛场景这种确定性很宝贵。把BFS和DFS的差异整理成表格一眼就能看出适用场景对比维度BFSDFS核心容器std::queue递归调用栈或显式stack遍历顺序按圈层扩散由近及远深入某一条分支到底再回头栈溢出风险无内存分配在堆上递归深度大时有明显风险最短步数支持天然支持第一次到达即最优需要额外处理可能会走很多弯路代码结构队列加循环结构固定递归写法简洁但边界条件容易漏适用场景最短路径、层级扩张、连通块染色连通性判断、路径枚举搜索当然如果DFS用显式栈实现递归深度问题可以规避代码结构和BFS也几乎一样只是容器从queue换成stack。不过既然标题是BFS_FloodFill下面全文都会围绕BFS展开DFS方案有需要的话另一个系列再聊。2. 队列加方向数组BFS FloodFill的C标准套路2.1 坐标建模与方向数组先别急着写代码拿到一道FloodFill题我建议先花30秒在草稿纸上把坐标系画出来。新手最常犯的错就是把题意里的“上下左右”和数组下标搞混。在二维数组grid中我们用grid[i][j]定位一个格子i表示行j表示列。往四个方向走一步分别是上grid[i-1][j]下grid[i1][j]左grid[i][j-1]右grid[i][j1]C里最标准的写法是定义两个常量数组int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};然后循环四次分别计算(nx, ny) (x dx[k], y dy[k])。dx负责行偏移dy负责列偏移两两配对正好是上、下、左、右。提示dx和dy的配对顺序别靠感觉写完后找个3x3的小矩阵实际走一遍。新手很容易把dx和dy写反导致原本上下左右的扩展变成了斜向跳跃代码查半天都查不出来。还有一点矩阵的行列数要在进入循环前取好int rows grid.size(); if (rows 0) return; int cols grid[0].size();这样后面判断边界时直接用nx rows、ny cols既清晰又不容易因为原地取size导致空矩阵崩溃。2.2 visited处理原则入队即标记FloodFill最怕什么同一个格子被反复入队最终形成死循环程序TLE到怀疑人生。要避免这一点必须有一个“这个格子我处理过了”的记录。实现上有两个主流选择一个是单独开一个bool visited[rows][cols]二维数组另一个是原地修改grid。原地修改的典型操作是把访问过的1改成一个不会再出现的值比如2或者变成0。原地修改的好处是省内存、代码短但坏处是会破坏原始数据在需要保留原始矩阵的场景里不能用。单独开visited更通用但多一个数组的开销。无论用哪种核心原则只有一个入队的那一刻就要标记不是出队时标记。想象一下A格子入队了但还没出队此时队列里还有另一个邻居BB在扩展时又发现A又把A塞进队列。一个A被几个邻居各塞一次队列里立刻出现多个A后面每个A又会把B和C各塞一次指数爆炸就来了。正确做法是在push之前或push的同时就把状态更新掉让“已经在队列里”这件事本身成为去过标记。2.3 一份可直接套用的BFS_Fill模板配合上面说的要点我给出一个最常用的模板目标是“一套代码改改条件就能过大部分FloodFill题”#include vector #include queue #include utility using namespace std; void bfsFill(vectorvectorint grid, int sr, int sc, int newColor) { int rows grid.size(); if (rows 0) return; int cols grid[0].size(); int oldColor grid[sr][sc]; if (oldColor newColor) return; queuepairint, int q; q.push({sr, sc}); grid[sr][sc] newColor; // 入队即标记 int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx rows || ny 0 || ny cols) continue; if (grid[nx][ny] oldColor) { grid[nx][ny] newColor; // 递补标记防止重复入队 q.push({nx, ny}); } } } }这段代码有几处细节值得单独讲oldColor newColor的判断是必须的。如果新颜色和老颜色相同比如都是2但起点已经被改成了2后续邻居判断时grid[nx][ny] 2这个条件仍然成立而它们又会被改成2——看起来没什么变化但整个连通块的格子全都会重复入队形成一个巨大死循环。边界判断写在最前面用continue跳过越界格子比把if包一层嵌套更清晰也更容易扩展成“八方向”版本。这里用的auto [x, y]结构化绑定需要C17。如果面试环境是C11改成int x q.front().first; int y q.front().second;即可逻辑完全一样。这个模板可以解决一批题图像渲染、岛屿数量、被围绕的区域、部分迷宫类问题只要把“条件”从“颜色相等”改成题目的具体规则其他部分几乎不用动。3. 从模板到题型五种常见变形与对应策略3.1 岛数量类统计连通块个数最经典的是LeetCode 200岛屿数量。给定一个由1和0组成的二维矩阵求陆地连通块的数量。这个题的思路非常直接遍历整个矩阵一旦遇到一个还没处理过的1就说明发现了一座新岛岛屿计数加一然后从这个格子出发BFS把整座岛的所有1全部标记为2或者0之后继续遍历。这里要注意外层双重循环和BFS的分工是不同的外层负责发现“新大陆”BFS负责“把一个大陆彻底走完”。如果漏了染色环节同一个陆地块会被外层遍历好几次计数就会虚高。这个“发现一次连通块全部处理”的套路是FloodFill最基础的应用也是对比并查集、DFS等解法时的基准问题。面试时如果被要求“写出多种解法”BFS版、DFS版、并查集版可以各来一套加分效果很明显。3.2 图像渲染类给你一个颜色替换任务LeetCode 733图像渲染就是画图工具油漆桶的代码版给定一个二维数组image起始坐标(sr, sc)把和起始点颜色相同且在同一个连通区域的所有格子统一替换成新颜色newColor。这道题的本质就是上面模板本身代码几乎可以原封不动套用。唯一的坑就是2.3提到的oldColor newColor问题。这种题很适合用来检验自己是否真的理解了BFS如果把四邻域改成八邻域你能不能立刻改对如果newColor和oldColor相同你怎么处理我一般建议刷题的时候每做完一题顺手改一改条件再做一遍比重复刷五道同类型题效率高得多。3.3 被围绕区域与边界扩散思维LeetCode 130“被围绕的区域”是一个很有代表性的变形。题目给一个二维网格里面有X和O要求把所有被X包围的O改成X。什么叫“被包围”如果一个O位于边界上或者通过其他O能连到边界那么它不会被包围因为它和外界是相通的。剩下的O才是真正被围住的。常规做法不是去检查每个O是否被围住而是反向思考从四条边界出发做BFS把所有能到达的O标记成#——这些是“不会被包围”的O。然后扫一遍全图剩下的O全部改成X最后再把#还原成O。这里的核心思路是从“边界可达”反推“内部被包围”比正向逐一判断简单得多但BFS模板完全没变变的只是起点集合不再是单个起点而是边界上所有符合条件的点。这种“从边界反向标记”的思想经常出现在矩阵连通性题目里比如太平洋大西洋水流问题、被包围区域问题掌握之后能省很多力。3.4 扫雷展开条件从“颜色相同”变成“规则命中”扫雷游戏LeetCode 529是FloodFill的进阶应用。给一个棋盘其中M代表未挖出的地雷E代表未挖出的空方块B代表已挖出的空白方块数字代表周围地雷数量。点击一个位置如果是地雷直接爆炸如果是空白方块且周围没有地雷它变成B并且继续递归展开周围所有E如果周围有地雷这个位置变成一个数字并停止展开。这里FloodFill的“条件”不再是简单的颜色相同而是一条业务规则只有“未挖出的空方块E”且“周围雷数为0”才继续扩散。要统计周围雷数得先写一个helper函数数一数八个方向的地雷个数。BFS结构照旧但入队条件从“颜色相等”变成了“规则命中”。这类题的训练价值在于让你学会把现实问题的规则翻译成BFS的入队条件而不是死记“颜色相等”这一种情况。3.5 分层BFS顺带求最短扩散距离FloodFill的另一种常见升级是分层统计。因为BFS天然一圈一圈向外扩散每一圈正好对应一个“步数”所以求最短步数、最小扩散轮数这类问题时BFS有天然优势。实现有两个办法一是开一个dist二维数组每次从(x, y)扩展到(nx, ny)时让dist[nx][ny] dist[x][y] 1最终dist里存的就是从起点到每个点的最短距离二是利用队列长度分层先记录当前队列里的节点个数cnt然后弹出cnt次这cnt个点都属于同一层处理完一层距离加一。注意这和纯FloodFill有一个细微差别纯FloodFill不需要记距离只要标记“访问过”分层统计则必须记录层数并且仍然要遵守“入队即标记”否则同一个点会被多条路径重复入队距离就乱了。很多二叉树层序遍历的题也是同一套思路只不过把二维矩阵换成了树节点。把几类常见题型的入队条件和标记方式放在一起对比思路会更清楚题目类型典型题目入队条件标记方式图像渲染LeetCode 733颜色与起点相同原地改色岛屿数量LeetCode 200当前值是1原地改成0被围绕区域LeetCode 130当前值是O临时改#最后还原扫雷展开LeetCode 529E且周围雷数为0改成B后再扩散最短距离/最短路径迷宫类格子可通行visited数组另记dist4. 实战两道经典题跟着完整走一遍4.1 图像渲染LeetCode 733完整实现我把上一章模板直接套到这道题上完整代码如下class Solution { public: vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) { int rows image.size(); if (rows 0) return image; int cols image[0].size(); int oldColor image[sr][sc]; if (oldColor color) return image; queuepairint, int q; q.push({sr, sc}); image[sr][sc] color; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx rows || ny 0 || ny cols) continue; if (image[nx][ny] oldColor) { image[nx][ny] color; q.push({nx, ny}); } } } return image; } };由于这个题允许原地修改所以没有额外开visited数组直接利用旧颜色和新颜色的差异来避免重复处理。有个细节值得多想一下为什么image[nx][ny] oldColor这个判断就已经起到了“visited”的作用因为一旦某个格子被入队它的颜色立刻被改成了新颜色后续任何邻居再看到它时它已经不等于oldColor了自然不会被再次入队。这种“靠修改值本身阻止重复”的技巧是FloodFill原地染色版能省内存的底层原因。为了验证代码正确性我习惯在脑子里跑一个小例子一个3x3矩阵起点在中心颜色全部相同。第一步中心染色并入队第二步弹出中心四个方向上色并入队第三步依次弹出这四个点每个点只会把自己的邻居染色但中心已经是新颜色不会被再次加入。整个过程每个格子恰好入队一次循环终止条件清晰。强烈建议新手也这样用纸笔推一遍比直接看代码背流程有效得多。4.2 岛屿数量LeetCode 200二维坐标压缩成int的技巧岛屿数量题我给出一个可能不太常见的写法把二维坐标压缩成一维int只用一个queue 在很多平台上比queuepairint,int更省内存、也更快尤其是在海量节点的时候。压缩办法很朴素给定一个cols列数的矩阵(x, y)这个坐标用id x * cols y来表示恢复时用x id / colsy id % cols。class Solution { public: int numIslands(vectorvectorchar grid) { int rows grid.size(); if (rows 0) return 0; int cols grid[0].size(); int count 0; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { count; queueint q; q.push(i * cols j); grid[i][j] 0; while (!q.empty()) { int id q.front(); q.pop(); int x id / cols; int y id % cols; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx rows || ny 0 || ny cols) continue; if (grid[nx][ny] 1) { grid[nx][ny] 0; q.push(nx * cols ny); } } } } } } return count; } };这个版本的核心技巧就一行id x * cols y。它的前提是cols在本题中固定不变且cols不为0。在网格较大的情况下int队列的元素占用比pairint,int小一半左右缓存命中率也更高。恢复坐标时除法和取模各一次Big-O层面可以忽略不计但在常数层面比pair稍微快一点。如果你刚开始学没必要为了这个技巧硬背先用pair版本跑通思路以后再逐步优化会更扎实。5. 排查实录FloodFill代码常见的坑与调试思路5.1 死循环大多是重复入队不是方向写错FloodFill最经典也最折磨人的问题就是超时而超时原因九成是同一个点被反复入队。最常见的写法失误是在扩张时先把点入队但忘了在入队的那一刻更新访问状态等到出队时才更新。这样就会导致同一个点被多个邻居发现、多次入队队列越来越大最终程序卡死。排查方法很直观在push语句前后加一行打印输出nx、ny和当前队列大小如果日志里出现大量重复坐标基本就是漏标记了。修复也很简单把标记动作挪到push前或者把“标记”直接表现为染色/修改原值就像前面模板那样。注意在BFS里“入队”本身就应该视为“已访问”。千万不要只写成出队时更新那是显式栈方案里可能能用、但BFS里特别容易出事的写法。5.2 起点条件漏判断直接TLE另一个容易翻车的点发生在入口处比如图像渲染题里如果newColor和oldColor相等你不提前返回则起点染色后颜色没变后续邻居判断仍然拿oldColor当条件整个连通块会被反复入队妥妥超时。类似地如果起点越界、矩阵为空代码也会在访问grid[0].size()那一行崩溃或者出现未定义行为。我写FloodFill类题目时开头固定会想三件事矩阵是否为空、起点是否合法、新旧值是否相等。这三条哪怕只占三行代码但对整道题能否AC起到决定性作用。更稳的做法是写一个isValid(x, y)辅助函数把边界判断集中到一起既降低漏判风险又让主循环代码更干净。5.3 坐标压缩时除法/取模的坑用id x * cols y做压缩时最容易出问题的不是压缩而是恢复。如果你忘记cols是题目里的列数或者错误地用了rows当除数轻则坐标错乱重则数组越界。另一个常见坑是当cols为0时id % cols直接在数学上就有问题所以前面必须先判断rows 0返回。这个坑平时刷题可能遇不到但一旦矩阵边界被修改或者你套用模板时换了问题就会突然出现。我的建议是面试阶段可读性优先先用pairint,int写如果确实遇到较大的矩阵再考虑int压缩并且压缩版本务必加注释说明id的组成格式。代码可读性在你回头复习时会给你省下大量时间。5.4 大矩阵下的空间与性能优化如果Grid很大比如一万乘一万空间上就不能再傻乎乎开O(RC)的visited数组了原地标记会更有优势如果题目不允许修改原矩阵可以用一个更省空间的技巧只存“本轮入队的点”坐标配合哈希集合去重虽然最坏情况下依然是O(RC)但实际运行时会省很多内存。不过这种优化通常只在竞赛题里才需要面试阶段能顺畅写出标准BFS、正确分析复杂度已经足够过关了。另外一个常见优化方向是用数组模拟队列。std::queue在反复push/pop时会有动态分配的开销如果你对性能敏感可以事先开一个大小至少为R*C的vector 作为队列用一个head指针和一个tail指针模拟入队出队vectorint q(rows * cols, 0); int head 0, tail 0; int startId sr * cols sc; q[tail] startId; while (head tail) { int id q[head]; // 出队后的扩展逻辑与std::queue版本完全一致 // 需要入队时执行 q[tail] nx * cols ny; }这种方法在OJ上经常能快不少但代码可读性会下降。我个人建议先把std::queue版本写对再考虑要不要优化不要一开始就整这些花活。最后聊点心得。FloodFill刚学的时候看起来像是“背模板”但实际上它的核心价值在于让你真正理解“图的遍历”这件事。很多二维矩阵题本质上都是把矩阵看作一个稀疏图每个格子是一个节点上下左右是边BFS、DFS、并查集都在做同一件事在图上找连通块。想通这一点之后你会发现刷题时很多题目都能统一到同一个框架下——这比记住某个特定题目的代码重要得多。我自己在带新人刷题时最推荐的做法是拿一张方格纸手动模拟一个5x5矩阵的BFS过程把每一步队列里的元素写出来。这个动作看起来慢但它能同时帮你搞定队列、visited、边界判断三个最容易出错的地方。等你模拟过三五道题再回头看本篇文章的模板会觉得那些代码不是背下来的而是顺理成章长出来的。