如果你用过画图软件里的油漆桶感受过那种“点一下一整片颜色哗地替换成新颜色”的效果那你已经见过FloodFill的现场了。这个算法广泛用在图像处理、扫雷展开、地图连通区域标记等场景而DFS深度优先搜索几乎成了解决FloodFill最直白的解法。很多朋友一听到“网格递归”就头疼其实FloodFill的代码套路非常固定真正让人翻车的往往不是算法本身而是几个判断顺序、染色时机的小细节。这篇文章就从“为什么FloodFill适合用DFS”讲起我会把一个能直接跑的递归模板拆开讲透再带你看几道高频变体题最后聊聊递归爆栈的应对思路和调试技巧。不管你是刚开始接触DFS的新手还是想快速复习网格连通性套路的老手读完之后基本都能自己写出一版干净的FloodFill。1. FloodFill是什么从油漆桶到扫雷的同一件事1.1 你感知过的FloodFill场景画图软件是理解FloodFill最好的入口。你选好一种颜色拿起油漆桶工具对着画布某个区域点一下整片和点击处颜色相同的相邻区域瞬间全部变成新颜色。这个过程看起来像是有颜色的“水”从你点击的位置向外蔓延凡是颜色相同又能连通的格子都被淹没碰到颜色不同的格子就停下来。扫雷游戏里的展开也是同一个逻辑点到空白格子时整片连通的空白格子会被一起翻开边缘上那些带数字的格子也会跟着暴露出来。如果你用过修图软件的魔棒工具或者玩过那种“点击消除同色方块”的小游戏本质上都在做同一件事——从一个种子点出发把所有满足“相邻”和“属性相同”两个条件的元素找出来统一换个状态。这就是FloodFill也叫洪水填充或种子填充。它并不只存在于算法题里而是实实在在活在每一款图形编辑器、每一个扫雷游戏、每一张地图的连通区域判断里。1.2 算法视角下的严格定义站在算法题的角度FloodFill通常这样描述给定一个二维数组也叫网格或矩阵再给一个起始坐标比如第sr行第sc列以及一个目标值newColor。你需要把起始坐标所在的“连通区域”内所有和grid[sr][sc]值相等的格子全部改成newColor。这里有两个关键条件缺一不可第一格子之间必须连通一般指上、下、左、右四个方向能走到第二格子的当前值必须等于起始点的旧值。换句话说只有同时满足“位置连通”和“属性相同”的格子才属于这次洪水该淹没的范围。而“洪水”向外蔓延的边界就是颜色不同的格子、数组边界以及已经被修改过的格子。1.3 为什么值得专门研究FloodFill被很多人归类为“入门算法”但它的价值一点都不入门。它是所有二维网格连通性问题的地基你后面遇到的岛屿数量、岛屿最大面积、被围绕的区域、扫雷扩散、矩阵连通分量看起来题目花样百出本质都是FloodFill的变体。我个人的体会是把DFS解决FloodFill这一套逻辑真正吃透比背十道独立题都有用。因为你拿到一个新网格题时第一反应应该是“能不能抽象成FloodFill”——如果能把问题转换成“从哪些点出发、按什么条件连通地标记区域”解题思路基本就打开一半了。这也是为什么很多教材把FloodFill放在DFS专题的第一个实战案例。2. 为什么DFS是解决FloodFill的首选方案2.1 DFS与BFS的路线之争FloodFill有两种主流解法一种是DFS一种是BFS宽度优先搜索。很多教程默认讲DFS并不是因为DFS在性能上碾压BFS而是因为在“找连通区域”这件事上DFS的写法和心智负担都更小。DFS借助系统调用栈完成回溯你只需要写一个递归函数函数内部处理“当前格子”和“四个邻居”即可BFS则需要你显式维护一个队列还要时刻注意“入队时就要标记访问过”稍不留神就会重复入队代码量一下就上去了。FloodFill本身不关心“从起点到某个格子最短需要几步”它只关心“哪些格子属于同一个连通块”这正是DFS擅长的领域。你可以把DFS想象成一个人执意沿着一条路走到黑走不动了再退回来换一条路而BFS是一圈一圈向外扩散像水波一样均匀推进。对于“标记整片区域”这个需求DFS的直来直去反而更省事。对比项DFSBFS额外数据结构依赖系统调用栈无需自建队列需要显式维护队列实现代码量递归写法很简短核心逻辑十几行队列加标记代码量略多遍历顺序一条分支走到底再返回从起点逐层向外扩散最短路径能力不适合天然适合找最短步数爆栈风险高递归深度受系统栈限制低队列不依赖系统栈2.2 递归背后那根暗线系统调用栈递归DFS之所以“自带回溯”是因为每一次调用自身之前当前函数的状态会被压入系统调用栈。比如你在dfs(row, col)里调用了dfs(row - 1, col)那外层这个(row, col)的状态会一直挂在栈上直到内层全部跑完它才会继续执行后面的代码。这个机制让“走到底再回头”变得极其自然——你不需要手动记录“刚才从哪个方向来的”系统栈帮你记着。但好处和风险是同一枚硬币的两面。系统栈的深度不是无限的尤其在一些语言和运行时环境里默认递归深度可能只有几千层。如果连通区域特别大比如一千行一千列全是相同颜色递归路径最坏可以走到上万层这时候程序会直接抛栈溢出错误。这也是后面我要专门讲“迭代版DFS”的原因你迟早会撞上这个场景。2.3 一个关键选择四方向还是八方向写FloodFill之前第一件事是确认题目里的“相邻”到底是四方向还是八方向。四方向就是上、下、左、右四个邻居方向数组长这样const directions [ [-1, 0], // 上 [1, 0], // 下 [0, -1], // 左 [0, 1] // 右 ];如果题目要求八方向也就是斜对角也算相邻就再补上四个组合[-1, -1]、[-1, 1]、[1, -1]、[1, 1]。这个选择直接决定连通区域的形状。图像填充类题目大多默认四方向但地图类题目偶尔会明确说“八个方向都算连通”读题时一定要先看清楚。方向数组的另一个好处是写循环方便不用把四个递归调用手写出来代码更整洁。3. 手写DFS洪水填充从递归模板到完整代码3.1 先搭骨架以大多数算法题都见过的floodFill(image, sr, sc, newColor)为例我习惯把整个流程拆成四步。第一步从起点取出旧颜色oldColor。第二步如果oldColor和newColor相同直接返回原数组这是一个很多人会漏掉的关键分支。第三步定义好边界变量rows和cols再写递归函数dfs。第四步从起点调用dfs结束后返回image。取出旧颜色这一步看着简单但它是整个算法的基准线。后面所有格子的判断都是“当前格子的值等不等于oldColor”而不是“等不等于某个固定数字”。这个基准线一旦取错整个连通区域都会判断错。所以代码第一行一定是const oldColor image[sr][sc]所有递归逻辑都围绕这个值展开。3.2 一个容易忽略的前置判断oldColor等于newColor的时候为什么要提前返回我给你演示一下不写这个分支会怎样起点颜色是红色新颜色也是红色进入dfs后当前格子颜色等于oldColor于是把它改成newColor也就是红色。可问题是改完之后它还是红色继续递归邻居邻居又等于oldColor改了以后还是红色于是无限递归下去最终栈溢出。切断这个死循环有两种做法。一种是提前判断颜色相同就直接返回另一种是“记录旧颜色后立即改色”的原子操作只要保证递归扩散前当前格子的颜色已经不等于旧颜色回路自然断开。LeetCode的官方题解也是先处理这个分支因为它最省心后续函数逻辑完全不用为“颜色相同”而特殊处理。3.3 完整代码与逐行拆解下面是一份可以直接跑的JavaScript递归模板配合LeetCode 733题“图像渲染”的测试用例没有问题var floodFill function(image, sr, sc, newColor) { const oldColor image[sr][sc]; if (oldColor newColor) return image; const rows image.length; const cols image[0].length; const dfs (row, col) { // 越界判断必须放在最前面 if (row 0 || row rows || col 0 || col cols) return; // 颜色不匹配不属于当前连通块 if (image[row][col] ! oldColor) return; // 先染色再扩散顺序不能反 image[row][col] newColor; dfs(row - 1, col); dfs(row 1, col); dfs(row, col - 1); dfs(row, col 1); }; dfs(sr, sc); return image; };这段代码的核心就四件事越界判断、颜色判定、染色标记、向四个方向递归。越界判断放最前面是因为后面要用image[row][col]访问数组下标都不合法了读出来的数据自然毫无意义。颜色不匹配的格子直接返回说明洪水到这里被“堤坝”挡住了。染色这一步其实同时完成了“标记已访问”的职责——因为染成新颜色后旧颜色就再也匹配不上了。3.4 时间与复杂度账从复杂度上看FloodFill的DFS解法非常划算。每个格子最多被访问一次因为一旦被染色它就再也不可能等于oldColor后续递归不会重复进入。所以时间复杂度是O(N×M)N是行数M是列数和网格面积成正比。空间复杂度主要消耗在递归栈上最坏情况下整张网格全都等于oldColor递归路径可能从起点一直延伸到网格尽头栈深度也能到N×M。在竞赛和刷题平台里网格规模通常在几百乘几百以内递归完全扛得住。但在真实项目里比如处理几千乘几千的位图递归路径就可能很危险。这不是算法错而是运行时栈深度的物理限制。理解了这部分复杂度你就能判断什么时候可以放心用递归模板什么时候应该切换到迭代版本。4. 避坑实录写FloodFill最容易翻车的四个点4.1 越界检查顺序先判边界再读内容我第一次写FloodFill就栽在越界检查的顺序上。当时我把if (image[row][col] ! oldColor) return;写在了边界判断前面结果递归访问到[-1][0]的时候JavaScript里只是拿到undefined还不会立刻报错要换成Java或者C这种写法直接抛数组越界异常。正确的顺序永远是先判断row和col是否在合法范围内再通过下标访问数组内容顺序反了等于拿一个非法地址去读内存。// 错误示范先访问数组再判断边界 if (image[row][col] ! oldColor) return; if (row 0 || row rows || col 0 || col cols) return;这种错误在刷题平台上报错时特别迷惑因为它不一定每次都会崩溃有时候只是静默地改变了行为。JS里访问负数下标返回undefinedaccess非法内存的行为有时看起来“还能跑”。但结果就是错的而且很难排查。我的习惯是无论题目数组边界是什么dfs函数开头第一行永远是边界判断。4.2 染色时机不对漏标visited必然死循环FloodFill死循环的另一个高发原因是visited标记和递归时机错位。有些朋友会想先检查四个邻居能走再递归递归进去再染色。这个思路本身没问题但实现时很容易漏掉“当前节点必须立刻标记”。假设你进入了一个格子没有立刻染色而是先去递归上方的邻居上方邻居又递归回你此时你的颜色还是oldColor于是两个人互相调用永无止境。所以标准动作是“一进函数就判定、就染色然后再向邻居扩散”。染色不只是修改颜色更是在这个网格上画了一道“已访问”的标记。你不需要额外的visited数组因为颜色本身就是状态。如果你坚持用独立的visited数组也请记住进入函数的第一时间就要把visited[row][col]置为true而不是等递归返回后再标记否则同样的循环回路会再次发生。4.3 大图血案递归深度与栈溢出讲一个实际点的问题如果网格是一条长长的蛇形结构DFS会沿着蛇身一路走到底递归深度可能高达几十万层。这种深度在任何常规运行时环境下都是灾难。LeetCode的测试用例通常比较温和但真实业务里处理高分辨率图像时一定要心里有数。这时候递归让位给显式栈也就是用数组自己模拟一个栈把要访问的坐标压进去循环直到栈空。迭代版DFS代码如下var floodFill function(image, sr, sc, newColor) { const oldColor image[sr][sc]; if (oldColor newColor) return image; const rows image.length; const cols image[0].length; const stack [[sr, sc]]; image[sr][sc] newColor; while (stack.length) { const [row, col] stack.pop(); const neighbors [ [row - 1, col], [row 1, col], [row, col - 1], [row, col 1] ]; for (const [nr, nc] of neighbors) { if (nr 0 || nr rows || nc 0 || nc cols) continue; if (image[nr][nc] ! oldColor) continue; image[nr][nc] newColor; stack.push([nr, nc]); } } return image; };注意迭代版里同样是“入栈前先染色”这一步防止同一个格子被重复压栈。显式栈本质上是把系统栈的工作自己接管了栈深度不再受运行时递归限制而是受内存大小限制通常能撑到千万级别。如果你在超大网格上必须用DFS思路就用这个版本兜底。4.4 原地震动还是复制副本最后还有一个容易被忽视的设计决策能不能在原始数组上直接改颜色大多数刷题场景是允许的函数返回修改后的数组就结束了。但有些题目后续还要用到原始数据比如你先要标记一片区域之后又需要依据旧颜色判断另一片区域如果一开始就把原数组改得面目全非后面就没了依据。这种时候你有两个选择新建一个visited二维数组只标记访问状态不改原数组或者先深拷贝一份grid在拷贝上做FloodFill。前者更省内存后者更好理解。我的建议是读题时先确认输出要求。如果允许原地修改那就原地改简单直接如果题目强调“不能修改原数组”或者后续逻辑依赖原始数据就老老实实开visited数组别偷懒。5. 从基础模板延伸三道高频变体题5.1 岛屿数量把染色换成清空计数LeetCode 200题“岛屿数量”是FloodFill最经典的变体。题目给一个二维网格1代表陆地0代表水让你统计岛屿数量。岛屿的定义就是上下左右连通的陆地。解法思路非常直接两层循环遍历所有格子只要遇到一个1计数加一然后从这个点做一次FloodFill把整座岛屿的1全部改成0相当于“淹没掉”这片陆地。function numIslands(grid) { let count 0; for (let r 0; r grid.length; r) { for (let c 0; c grid[0].length; c) { if (grid[r][c] 1) { count; dfs(grid, r, c); } } } return count; } function dfs(grid, r, c) { if (r 0 || r grid.length || c 0 || c grid[0].length) return; if (grid[r][c] 0) return; grid[r][c] 0; dfs(grid, r - 1, c); dfs(grid, r 1, c); dfs(grid, r, c - 1); dfs(grid, r, c 1); }这个题的巧妙之处在于FloodFill不再只是“改变颜色”而是变成了“删除整块连通区域”。每执行一次FloodFill就是把一座岛从地图上抹掉下次循环再也看不到它。把模板里的newColor换成0把“判断相等”换成“判断是陆地”一个全新的算法题就解决了。5.2 岛屿最大面积让DFS返回数值岛屿最大面积这题就是在“岛屿数量”的基础上要求你算出所有岛屿中最大面积是多少。做法依然是用两层循环找到陆地但对每个岛屿执行FloodFill时DFS不再只是闷头标记而是需要带一个返回值统计它一共淹没了多少个格子。function maxAreaOfIsland(grid) { let maxArea 0; const rows grid.length; const cols grid[0].length; const dfs (r, c) { if (r 0 || r rows || c 0 || c cols) return 0; if (grid[r][c] ! 1) return 0; grid[r][c] 0; let total 1; total dfs(r - 1, c); total dfs(r 1, c); total dfs(r, c - 1); total dfs(r, c 1); return total; }; for (let r 0; r rows; r) { for (let c 0; c cols; c) { if (grid[r][c] 1) { maxArea Math.max(maxArea, dfs(r, c)); } } } return maxArea; }把返回值加进去之后FloodFill的“扩散”就变成了“收集”的过程。每个格子贡献1递归返回时累加最终返回的就是整个连通区域的面积。这里的核心思想是DFS不仅能改数据还能把沿途的统计结果带回来。掌握了这个写法以后遇到“连通块大小”“路径长度”类问题你都能直接用。5.3 被围绕的区域逆向思维LeetCode 130题“被围绕的区域”是FloodFill另一个经典应用。题目给一个包含X和O的网格要求把所有被X包围的O改成X但边界上的O及其连通的O不能被修改。如果你正向去想“哪些O是被包围的”需要先完整遍历每一个O的连通块再判断它是否接触边界逻辑绕且容易错。更聪明的做法是反向思考与其找“被包围的O”不如先排除“不能被改的O”。具体分三步。第一步从网格四条边上的每一个O出发做一次FloodFill把这些边界相连的O临时标记成#。第二步遍历整个网格把所有还保留为O的格子都改成X因为凡是能连通到边界的O已经在第一步被标记掉了。第三步把#还原为O。这个套路一旦记住以后遇到“找内部连通块”或“排除边界连通块”的题你都能直接套用。6. 调试技巧与进一步优化6.1 把网格打印出来看变化调试递归算法最怕“脑内模拟”。FloodFill的递归链很长想凭直觉确认哪里出错很不现实。我的做法是在dfs函数里加一行调试输出打印当前处理的坐标和染色后的值如果还看不清楚就在每层染色的地方打印整个网格的快照。这样你能直观地看到洪水是怎么一步步扩散的也能立刻发现某个方向没被访问、某个格子被重复处理之类的问题。console.log(访问: (${row}, ${col}), 当前颜色: ${image[row][col]});调试输出只在开发阶段保留提交前记得删掉。另一个有用的技巧是故意把网格打印成带边框的方阵用不同字符代表不同颜色人眼扫一眼就能定位异常区域。字符串调试法对二维网格题非常有效远比你盯着变量列表猜来猜去快。6.2 边界用例清单写完FloodFill我会先跑几个固定用例相当于“算法自检清单”。第一1×1网格只有一个格子正确结果应该直接把起点颜色改成新颜色。第二整张网格颜色完全相同这时候要确认会不会死循环正确行为是全部改成新颜色后正常结束。第三起点放在网格的四个角上检查越界分支是否被完全挡住。第四空数组或者只有一行、一列的窄网格这些极端形状最容易暴露边界判断的漏洞。用例考察重点1×1网格基本逻辑是否正常、是否越界整图同色是否死循环、是否预判oldColor等于newColor起点在四角向外两个方向的越界分支是否被挡住空数组或单行单列边界条件、rows/cols是否为0这套用例我建议你保存下来不只是FloodFill适用几乎所有二维网格DFS题都可以先跑一遍这些边界。很多看起来玄妙的bug其实就是“角落里的格子访问到-1下标”这种低级问题。6.3 超大图上的进一步优化如果你的目标不是刷题而是做图形编辑器或游戏引擎里的填充工具那纯DFS递归可能还不够。业界更常用的优化方案是扫描线填充每次处理一整条水平线段而不是一个格子一个格子地递归只有当线段端点遇到新区域时才继续扩散。这种方式把递归调用的次数从“每个格子一次”降到“每个连通线段一次”性能提升非常明显尤其在高分辨率图像上。但从学习路径来说我不建议一上来就啃扫描线算法。先把这个十几行的DFS递归模板吃透理解“越界、判断、染色、扩散”四件事的因果关系再去看扫描线优化你会更容易理解它到底优化了什么。FloodFill最大的价值不是让你背一个模板而是让你建立“网格连通性问题可以统一处理”的思维模型这才是应对算法题和真实项目的底层能力。最后再说一点我自己的体会。FloodFill代码很短但它的“短”掩盖了很多设计决策为什么先判断颜色相同为什么先染色再递归为什么边界判断必须放最前面。这些细节单独拎出来每一个都很简单合在一起就成了新手最容易踩的坑。我学这个算法时也经历过“照着模板抄都抄错”的阶段后来发现只要把每一行的执行顺序和原因都讲清楚就再也不会写错了。希望你读完这篇也能达到这种状态。