从画图工具到算法题BFS解决FloodFill算法的完整复盘如果你用过Windows画图板里的“油漆桶”工具点一下就能把一片相同颜色的区域全部换色其背后的核心算法就是FloodFill泛洪填充。而这个经典算法最常见的实现方式之一就是今天要聊的BFS广度优先搜索。把“从一个点出发扩散到所有连通且满足条件的格子”这件事讲清楚是理解BFS的关键入门路径也是面试里岛屿类问题、连通块问题的万能钥匙。这篇内容围绕BFS解决FloodFill算法展开适合刚接触算法基础、正在刷LeetCode的初学者也适合想系统梳理BFS应用场景的选手。我会先讲清楚思路为什么这么设计再给出完整可跑的代码然后通过三道经典题目带你把套路内化最后分享我实际踩过的坑和排查心得。只要你跟着走一遍再看任何FloodFill变种题都会觉得眼熟。1. 整体思路拆解为什么FloodFill要用BFS1.1 从“油漆桶”看泛洪填充的问题本质先想想画图板里的那个油漆桶。你点击某个像素点程序要做的事是找到所有与这个像素点颜色相同、并且通过相邻关系连通的像素把这些像素全部换成一个新颜色。这不是把所有相同颜色的像素都换色而是只换“和点击点连成一片”的那部分。这一片区域算法上叫连通分量。举一个通俗的例子。一张地图上有几个互不相连的湖泊你点击其中一个湖泊任一点油漆桶只会填满这个湖泊不会跨过陆地跑到另一个湖泊里。判断“是不是同一个湖泊”靠的是像素之间的相邻关系而不是颜色相同这个单一条件。所以FloodFill要做的事有两个核心步骤第一步从起点出发向外一层一层找邻居第二步判断邻居是否满足“颜色相同且未被访问过”。找到的就纳入填充区然后继续从这些新纳入的点向外扩展。这个过程天然就是一层一层扩散的结构和BFS的层级遍历思路完全吻合。1.2 BFS和DFS都能做为什么我推荐BFSFloodFill用DFS也能做网上很多题解也都是递归写法代码甚至可以写得更短。但我在实际写题和做项目时绝大多数情况下优先选择BFS原因有三点。第一个原因是递归深度。DFS靠函数递归栈实现如果地图是2000乘2000的全连通区域递归深度可能达到百万级别直接栈溢出。BFS用的是显式的队列内存只和区域周长相关不会爆栈稳定得多。第二个原因是层级扩散更符合直觉。BFS从起点开始先处理距离为1的格子再处理距离为2的格子一层一层往外走对“区域边界”的感知更清晰。比如扫雷游戏里点击空白格后需要展开一大片零散格子BFS的自然语义就是“逐层展开”。第三个原因是代码风格统一。BFS的基本框架是一套固定的模板初始化队列取出队首处理邻居入队。这套模板在最短路径、拓扑排序、层序遍历里都是同一套骨架。练熟这一套以后换场景只需要改判断条件和处理逻辑即可。1.3 连通性定义四连通和八连通FloodFill里必须搞清楚什么是“相邻”。最常用的是四连通也就是上下左右四个方向对应列偏移数组d {0, 0, 1, -1}和行偏移数组r {1, -1, 0, 0}。画图软件里的油漆桶默认就是四连通你在左上角点击不会斜着填到右下角的相邻格子。八连通则额外包含左上、左下、右上、右下四个斜方向。八连通区域的连通性判断更加宽松比如计算一块地形图里的岛屿数量时斜向相接的两块陆地算不算同一块岛取决于题目描述。这个细节决定代码里方向数组的长度和遍历次数写题前一定要先确认题目要求的是四连通还是八连通否则答案必然错。我处理过的一个典型坑是LeetCode 200岛屿数量默认是四连通但有些同学想当然用八方向遍历最后多算或少算了一堆块。永远先读题再动手。2. 画图画到一半停了核心实现步骤全解2.1 像素点状态怎么定义FloodFill整个过程需要记录每个格子处于什么状态。我把状态分为三类未访问、已入队、已处理。其实只要区分“是否需要访问”就够了因为在BFS里入队的同时就可以认定这个格子已经被覆盖了。在具体实现上最简单的方式是直接修改原数组。比如颜色填充场景被填充过的格子颜色已经改为新颜色这个新颜色本身就充当了“已访问”的标记。岛屿数量问题里访问过的陆地可以改为0避免重复计数。这种原地标记法省掉了一个额外的visited数组空间复杂度从O(m*n)降为O(1)不考虑队列本身。有一种情况必须单独处理新颜色和原始颜色相同。如果起始像素的原始颜色已经是目标颜色你还在BFS里做判断“与原颜色相同就填新颜色”会导致无限循环因为填充后还是原颜色永远满足条件。网上不少题解没提这个坑实际写代码的时候特别容易忽略。处理方法是在开头加一个特判起始颜色等于目标颜色时直接返回原数组。2.2 标准BFS模板队列操作必须熟练BFS解决FloodFill的模板非常固定我把它总结成四个步骤手写代码时按这个节奏来不会乱。// C 标准BFS FloodFill模板 class Solution { public: vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) { int oldColor image[sr][sc]; if (oldColor color) return image; int m image.size(), n image[0].size(); int dr[4] {0, 0, 1, -1}; int dc[4] {1, -1, 0, 0}; queuepairint, int q; q.push({sr, sc}); image[sr][sc] color; while (!q.empty()) { auto [r, c] q.front(); q.pop(); for (int i 0; i 4; i) { int nr r dr[i]; int nc c dc[i]; if (nr 0 || nr m || nc 0 || nc n) continue; if (image[nr][nc] ! oldColor) continue; image[nr][nc] color; q.push({nr, nc}); } } return image; } };Python版本的套路完全一致只是队列用deque实现from collections import deque def floodFill(image, sr, sc, color): old image[sr][sc] if old color: return image m, n len(image), len(image[0]) dr, dc [0, 0, 1, -1], [1, -1, 0, 0] q deque([(sr, sc)]) image[sr][sc] color while q: r, c q.popleft() for i in range(4): nr, nc r dr[i], c dc[i] if 0 nr m and 0 nc n and image[nr][nc] old: image[nr][nc] color q.append((nr, nc)) return image读代码时注意几个关键点获取元素坐标用q.front()弹出用q.pop()方向数组长度必须和连通性定义一致入队前先改状态防止同一个格子被重复入队。2.3 原地标记的细节决定了程序生死很多人写BFS第一步就错了错在把“入队”和“标记”分成了两步。正确做法是在向队列压入邻居节点时立刻标记这个邻居已经访问过比如立刻把颜色改掉。如果你等它出队的时候再改那么在出队之前这个格子可能会被其他相邻格子再次入队导致队列里出现大量重复元素算法退化甚至死循环。拿一个简单例子说明。起点是格子AA的右边是格子B下边是格子C。如果入队B和C时不改颜色B出队时发现右边和下面的像素颜色没变又把C入队了一次C出队时又会把B入队一次于是队列中B和C交替出现永远处理不完。这就是经典的“重复入队死循环”。原地标记带来的另一个好处是最终效果直接落在原数组上。LeetCode 733题直接返回image数组即可不需要额外构建结果数组。要注意的是一旦改了原数组后续判断“和oldColor相同”就不会误伤已经被填充的格子天然实现了剪枝。3. 三道经典题实操BFS FloodFill套路直接用3.1 图像渲染最直接的FloodFill原型LeetCode 733题“图像渲染”就是上面代码的原题。输入一个二维数组image给定起点坐标(sr, sc)和目标颜色color把起始像素所在连通区域内所有像素都改成目标颜色。这道题本质就是FloodFill的基本实现我建议你直接背诵模板闭着眼也能写对。题解里常说的“渲染”其实就是连通区域换色。需要注意的只有一个地方题目里把数组叫image里面存的是像素颜色值但这对算法本身没有任何影响二维数组里存的是什么都一样整数数组、字符数组都可。我自己面试遇到过把这题改写成“给定一个矩阵把最大的连通块找出来”的问题方法就是把所有连通区域都遍历一遍统计最大面积。BFS模板稍微改一下每搜完一个连通区域就更新最大值完全复用同一套结构。3.2 岛屿数量连通块计数的经典变种LeetCode 200题“岛屿数量”是FloodFill最出名的变种。输入一个grid格子的值是1或0连在一起的1构成一座岛屿统计岛屿总数。解决思路是遍历整个网格遇到一个1就把它当成一次BFS的起点岛屿数量加1用BFS把这一整块连通区域全部标记为0。标记完以后继续遍历后面的格子遇到新的1再启动新的一次BFS。下面是完整实现from collections import deque def numIslands(grid): if not grid: return 0 m, n len(grid), len(grid[0]) dr, dc [0, 0, 1, -1], [1, -1, 0, 0] count 0 for i in range(m): for j in range(n): if grid[i][j] 1: count 1 q deque([(i, j)]) grid[i][j] 0 while q: r, c q.popleft() for k in range(4): nr, nc r dr[k], c dc[k] if 0 nr m and 0 nc n and grid[nr][nc] 1: grid[nr][nc] 0 q.append((nr, nc)) return count这个解法的时间复杂度O(mn)每个格子最多入队一次、出队一次空间复杂度最坏情况下O(mn)即整个网格全是陆地时队列长度可能达到网格大小这是理想状态下BFS的极限。重点体会“外层遍历内层BFS”的组合模式这个模式会反复出现在各种连通块统计题里。3.3 被围绕的区域从边缘反向BFS的高级应用LeetCode 130题“被围绕的区域”是FloodFill思路的进阶应用也是面试里区分理解深度的分水岭。题目是这样的给定一个矩阵包含O和X把被X包围的O全部改成X。注意边界上的O不会被完全包围因此不能修改。正难则反。与其找哪些O被X包围不如找哪些O不能被包围。所有与边界上的O相连的O都不能被改剩下的O必然被X包围。所以先从四条边界上的O出发做BFS全部标记为“安全”然后遍历整个矩阵把未被标记的O改成X即可。class Solution { public: void solve(vectorvectorchar board) { int m board.size(), n board[0].size(); int dr[4] {0, 0, 1, -1}; int dc[4] {1, -1, 0, 0}; queuepairint, int q; // 把边界上的O全部入队 for (int i 0; i m; i) { if (board[i][0] O) { board[i][0] S; q.push({i, 0}); } if (board[i][n-1] O) { board[i][n-1] S; q.push({i, n-1}); } } for (int j 0; j n; j) { if (board[0][j] O) { board[0][j] S; q.push({0, j}); } if (board[m-1][j] O) { board[m-1][j] S; q.push({m-1, j}); } } // 从所有边界O出发BFS标记所有连通的O为S while (!q.empty()) { auto [r, c] q.front(); q.pop(); for (int k 0; k 4; k) { int nr r dr[k], nc c dc[k]; if (nr 0 || nr m || nc 0 || nc n) continue; if (board[nr][nc] O) { board[nr][nc] S; q.push({nr, nc}); } } } // 遍历全图O改成XS改回O for (int i 0; i m; i) { for (int j 0; j n; j) { if (board[i][j] O) board[i][j] X; else if (board[i][j] S) board[i][j] O; } } } };这里额外用了S做临时标记避免额外开visited数组。这个“标记中间态”的技巧在矩阵类算法里非常常用学会了能省不少空间和代码量。4. 常见问题与排查技巧我踩过的那些坑4.1 死循环的三大元凶FloodFill写成死循环绝大多数原因不外乎三个忘记判断边界条件、没有在入队时立即标记、数组下标越界。其中“忘记标记”最隐蔽因为代码看起来毫发无损逻辑上却必然死循环。排查死循环有一个很实用的经验在循环体内加一个计数器超过格子总数就强制退出。比如在主循环里写if (cnt m * n) break;再配合打印出队坐标几分钟就能定位问题出在哪一步。这个方法在真实调试时比干瞪眼效率高得多。4.2 栈溢出与TLE不是一回事用DFS递归实现FloodFill时大图用例必挂报错叫栈溢出Stack Overflow。用BFS时一般不爆栈但如果队列中重复元素过多会触发超时TLE。这两种错误背后的根因完全不同排查思路也要分开。栈溢出的本质是递归深度不可控解决办法是改成显式的栈或队列也就是用BFS或手动栈DFS。TLE的本质是算法复杂度退化常见原因是重复入队导致每个格子被访问多次优化方向就是坚持“入队即标记”保证每个格子只被处理一次。从时间复杂度角度FloodFill就地标记后严格为O(m*n)一旦你发现运行时间远超这个量级第一反应就应该检查是否重复入队。4.3 边界判断的隐藏陷阱方向数组循环里的越界判断有个常见问题先取nr和nc再判断它们是否越界这个顺序不能反。如果你先在循环里用nr和nc访问了数组再去判断越界就会出现数组越界异常。正确写法是越界判断写在前用continue跳过非法坐标。另一个边界陷阱是题目给的起点坐标可能非法虽然LeetCode默认输入起点合法但在工程项目里必须做防御性处理。我自己的习惯是在任何函数入口先检查起点坐标是否在矩阵范围内不在就直接返回输入原样。这个习惯花不了几行代码但能避免线上环境里偶发的崩溃。4.4 八连通误用和颜色比较的类型问题很多题在连通性定义上做文章FloodFill的连通性默认是四连通但有些变种题明确要求八连通。如果你背模板时没注意多写或少写四个方向数组整道题的答案全部是错的。我的做法是每次写新题前先把题目里的“相邻”定义圈出来再选择方向数组。颜色比较方面要注意矩阵存的是整数用直接比较即可没问题。如果矩阵存的是浮点数比较相等时要带精度容忍比如abs(a - b) 1e-6。另一个容易忽略的点是目标颜色和原颜色相同前面提过这个情况必须特判否则无限循环。4.5 参数传递与引用修改的坑C里如果你不用引用传入vectorvector 而是按值传参那么函数内部对image的所有修改都不会反映到外部题目会判错。Python则不存在这个问题因为列表是可变对象函数内修改会直接作用于原列表。这是语言特性的坑写C的同学要特别注意函数签名。Java语言里二维数组是引用类型也天然支持原地修改但要注意不要用clone之类的方法复制数组否则又回到了“改了没生效”的尴尬。5. 深入一点FloodFill的现实应用与扩展思考5.1 图像编辑和扫雷里的FloodFill画图工具的油漆桶是FloodFill最直白的应用这在前面已经讲过。另一个经典场景是扫雷游戏里点击空白格时展开周围一大片区域这也是FloodFill只是条件是“当前格是空白格且未被翻开”一旦遇到数字格就停下来。从工程角度真正的图像编辑软件里的油漆桶要比这复杂得多会考虑颜色相似度阈值、容差、抗锯齿等因素。算法核心仍然是BFS或DFS只是在颜色相等判断上改成了距离判断这也解释了为什么这个算法能一直沿用到今天因为框架是稳定不变的。5.2 连通区域分析从ACM竞赛到计算机视觉在计算机视觉里连通区域标记也是一个基础操作用来把图像中像素值相近、空间相邻的区域提取出来。教科书的经典实现是Two-Pass算法但同样可以基于FloodFill做。当你把一幅图像读成矩阵后对每个未访问的目标像素跑一次BFS就能得到一块完整连通区域然后再统计面积、外接矩形等特征。用FloodFill做连通区域分析的优点是只遍历一次矩阵且天然适用于交互式点击指定区域的场景。5.3 扫一眼即可识别变种题学会了FloodFill这个套路你会发现大量题目都可以用同样的框架解决比如岛屿最大面积在BFS过程中统计连通块大小更新最大值太平洋大西洋水流问题从四个方向边界反向BFS和130题几乎一模一样被围绕的区域边界反向BFS标记图片平滑器依稀是FloodFill变种只是少了连通性扩散我自己的识别方法是只要题目里出现“从某个点出发、扩散到连通的区域、按条件改变状态”大概率就是FloodFill思维。先确认连通性定义再确认是否允许原地修改直接套模板就好。6. 一个实操技巧用BFS写水洼计数最后再分享一个我在实际项目里常用来验证BFS FloodFill理解的练手小场景叫“水洼计数”。假设给你一个二维字符矩阵W表示积水.表示干燥地面所有水平垂直相邻的W构成一个水洼统计一共有多少水洼。这和LeetCode 200岛屿数量没有任何区别但拿它来做本地练习的好处是你可以快速生成随机数据验证正确性比如1000乘1000的随机矩阵跑一次检查结果是否符合预期。自己写一个小脚本对比暴力判断结果和BFS结果对理解边界情况和稳定性非常有帮助。def count_puddles(grid): m, n len(grid), len(grid[0]) dr, dc [0, 0, 1, -1], [1, -1, 0, 0] ans 0 from collections import deque for i in range(m): for j in range(n): if grid[i][j] W: ans 1 grid[i][j] . q deque([(i, j)]) while q: r, c q.popleft() for k in range(4): nr, nc r dr[k], c dc[k] if 0 nr m and 0 nc n and grid[nr][nc] W: grid[nr][nc] . q.append((nr, nc)) return ans我拿这个场景做实验时发现一个有意思的问题当你把矩阵改得全是W时BFS的队列长度会先涨到接近整个矩阵大小然后慢慢下降。这个时候你就能直观感受到为什么最坏空间复杂度是O(m*n)而不是O(1)。自己跑一跑比背概念深刻得多。按我刷题的经验BFS解决FloodFill这套东西只要你把模板练到“闭着眼能写”再把上面几个经典变形题做一遍基本就能把这一类题目一网打尽。遇到新题先别慌确认连通性、确认能否原地修改、套模板、加边界判断四步走完一般不会出大问题。
