算法奇妙屋写到第三十二期，这次聊聊一个很常见、但很多新手第一眼会懵的题目类型：floodfill。也就是所谓的“洪水填充”，给一个起点，像水漫开一样把满足条件的连通区域全部“染色”。无论是刷题碰到的图像渲染、岛屿数量，还是日常开发里的画图板油漆桶、扫雷翻格子，底层都是同一套逻辑。而这其中，用 DFS（深度优先搜索）去实现 floodfill 是我个人最推荐的方式，代码短、思路直、容易调试。这篇文章就从原理、模板、经典例题到常见翻车点，完整梳理一遍。
1. floodfill 到底在解决什么问题，为什么 DFS 是首选
1.1 从一个填色需求说起
先别急着看代码，先想一个生活场景。你打开一个最简单的位图编辑器，拿油漆桶工具点一下图片里的某个纯色区域，这个区域瞬间全变成新颜色。这个操作的本质是什么？是从你点击的那个像素出发，不断向上下左右扩散，凡是颜色和你点击处相同、并且连在一起的像素，全部改成新颜色。这就是 floodfill。
放到算法题里，问题往往被抽象成：给定一个二维网格（m x n），网格里每个格子有某种状态（数字、颜色、字符等），从某个起点出发，把与该起点相邻且状态相同的所有格子找出来，并按需求统计数量、改变状态、或者判断边界。经典的题目有 LeetCode 733（图像渲染）、200（岛屿数量）、130（被围绕的区域），以及蓝桥杯等竞赛里的许多迷宫类、连通块类问题。
这套东西之所以叫“洪水填充”，是因为扩散方式很像水在低处蔓延：遇到同色的继续走，遇到不同色的就停，直到这个连通区全都走完。
1.2 DFS 为什么天然匹配 floodfill
解决 floodfill 有两条主流路线：DFS 和 BFS（广度优先搜索）。很多人习惯一上来就套 BFS 的队列模板，因为“层序遍历”听起来更稳。但就 floodfill 这类“整块区域染色”的问题来说，DFS 有它的天然优势。
DFS 的思路是一条路走到黑：从起点出发，先往一个方向一路深入，直到撞上边界或者不同色，再回头走下一个方向。这个“走到头再回溯”的过程，和递归函数调用栈的模式完全吻合。你写一个递归函数，函数里先处理当前格子，然后依次对上下左右四个邻居递归调用同一个函数。每调用一层，就相当于往洪水里推进一步。代码量非常少，核心逻辑也就十几行。
BFS 也不是不行，它的优势在于可以记录“第几步到达某个格子”，所以更适合求最短路径。但你如果只是想把一个连通区域全部标记一遍，BFS 还要额外维护一个队列，写法反而绕。用 DFS 处理 floodfill，你会发现代码几乎可以照着模板默写，这也是为什么许多算法模板书把它归类为“入门必会”题型。
1.3 floodfill 的三个核心要素
不管题目包装成什么样，floodfill 都绕不开三个要素：
第一个是“起点”。也就是种子点，你从哪里开始漫灌。可能题目直接给定坐标，也可能需要你遍历全图自己找起点（比如岛屿数量题里，每个未被访问的“1”都可以当作新岛屿的种子）。
第二个是“扩散规则”。通常指四方向（上、下、左、右）或八方向（再加上四个斜对角），并且要满足目标格子的状态与种子格子的状态一致，或者满足题目特定的条件。这里的“一致”具体是什么，每道题有每道题的说法，可能是颜色值相同、数字相同、字符相同。
第三个是“终止条件”。什么时候停止递归？最常见的是越界，以及不满足颜色/状态条件。另一个容易被忽略的是“已经访问过”。如果没有访问标记，DFS 会陷入无限循环：A 访问了右边的 B，B 左边的邻居又是 A，于是又回到 A，周而复始。
把这三个要素想清楚，floodfill 的代码基本就是套模板的事了。
2. 核心细节解析与实操要点
2.1 第一步：把二维网格当成图来遍历
很多初学者看到“二维数组”就走不出数组思维，总想着怎么用循环嵌套搞定。其实 floodfill 的底层是个图遍历问题：二维网格上的每个格子都是一个节点，上下左右相邻的格子之间有一条边，这条边是否“可走”，取决于两个格子的状态是否一致。
一旦建立了这个认知，代码结构就清晰了。我们不需要真的去建一个邻接表或邻接矩阵，只需要知道怎么从当前格子找到它的邻居。通常用两个方向数组：
int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1};这样在递归函数里，一个 for 循环就能枚举四个邻居：
for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (check(nx, ny)) dfs(nx, ny); }如果你需要八方向连通（比如扫雷的周围八个格子），只需要把方向数组扩成八个：
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};2.2 访问标记，用额外数组还是原地修改
这是 floodfill 里最关键的细节之一。防止重复访问的办法有两种。
第一种是开一个 boolean 二维数组visited，记录哪些格子已经走过了。优点是原数据不动，保留现场；缺点是额外占空间，而且多写几行代码。
第二种是“原地修改”，直接把访问过的格子改成一个新的值。比如在岛屿数量那道题里，通常把访问过的'1'改成'0'，这样下次遍历就不会再碰到它了。再比如在图像渲染题里，把旧颜色覆盖成新颜色，本身也是一种标记。这样省掉了 visited 数组，代码更简洁。
我个人的经验是：如果你只是想统计连通块大小或个数，原地修改基本是首选，前提是你不介意原始数据被破坏；如果题目要求保留原始网格，或者需要在之后多次访问数据，那就老实开 visited 数组。同一个 dfs 模板，换一下标记方式就可以了。
2.3 递归模板：先标记，再递归
下面给出一份最标准的 DFS floodfill 模板，这里用 C++ 写：
void dfs(vector<vector<int>>& grid, int x, int y, int oldColor, int newColor) { // 1. 越界或颜色不匹配，直接返回 if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size()) return; if (grid[x][y] != oldColor) return; // 2. 标记 / 染色 grid[x][y] = newColor; // 3. 递归访问四个方向 dfs(grid, x + 1, y, oldColor, newColor); dfs(grid, x - 1, y, oldColor, newColor); dfs(grid, x, y + 1, oldColor, newColor); dfs(grid, x, y - 1, oldColor, newColor); }这份模板的每一行都有讲究。越界判断必须写在整个函数的最前面，因为在访问grid[x][y]之前，必须确认 x、y 没有超出数组范围，否则会下标越界。颜色不匹配的判断紧随其后，这一步相当于“剪枝”，把不满足扩散条件的路径直接砍掉。然后立刻修改当前格子的颜色，这一步同时承担了“访问标记”的作用，避免回踩。最后分别向四个方向递归。
这里有一个新手特别容易犯的错：先递归再标记，或者标记放在递归后面。如果标记在递归后面，那么第一个格子在递归还没回来时仍然保持着旧颜色，它的邻居递归回来时还可能再次访问它，造成死循环。所以记住一句话：进入格子后，第一件事就是标记。
2.4 额外状态与“剪枝”在 floodfill 里的含义
很多刷题教程一提到“剪枝”就想到回溯算法、DFS 剪枝，其实在 floodfill 里也有剪枝，只是形式非常朴素：颜色不匹配就不再深入。上面模板里的if (grid[x][y] != oldColor) return;就是剪枝，它保证了搜索空间被限制在连通区域内部，不会盲目扩散到整个网格。
如果你遇到的是更复杂的版本，比如“需要在 floodfill 过程中记录路径”或“连通区域里存在多种状态”，可以给每个格子定义状态：0 表示未访问，1 表示待扩散，2 表示已经处理完。这样可以配合回溯做一些更精细的控制，但六成以上的题目用最基本的模板就足够了。
3. 实操过程与核心环节实现
3.1 经典题一：图像渲染（LeetCode 733）
题目大意是：给定一个二维网格image，以及一个起点坐标和新的颜色值，把与起点颜色相同且相连的所有格子的颜色全部改成新颜色。这几乎就是 floodfill 的定义，直接套模板：
class Solution { public: vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) { int oldColor = image[sr][sc]; if (oldColor == newColor) return image; // 老颜色和新颜色一样，没必要操作 dfs(image, sr, sc, oldColor, newColor); return image; } void dfs(vector<vector<int>>& image, int x, int y, int oldColor, int newColor) { if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size()) return; if (image[x][y] != oldColor) return; image[x][y] = newColor; dfs(image, x + 1, y, oldColor, newColor); dfs(image, x - 1, y, oldColor, newColor); dfs(image, x, y + 1, oldColor, newColor); dfs(image, x, y - 1, oldColor, newColor); } };注意那个oldColor == newColor的提前判断。如果不加，DFS 进入后把当前格子改成新颜色，然后递归邻居。邻居判断时，如果 oldColor 等于 newColor，那么邻居检查grid[nx][ny] != oldColor时，其实改过色的格子和没改过色的格子颜色一样，会造成重复访问，直到栈溢出。这个细节很隐蔽，但几乎每家公司的笔试里都有可能在测试用例里埋这个坑。
3.2 经典题二：岛屿数量（LeetCode 200）
这类题换了个包装：二维字符数组里，'1'表示陆地，'0'表示海水。问你一共有几块连在一起的陆地。这里的“连在一起”是四方向相邻。思路很简单：遍历整个网格，每遇到一个'1'，就把它当作一块岛的起点，count 加一，然后用 floodfill 把这个岛的所有陆地都“消灭掉”（改成'0'）。下次遍历就不会再遇到同一块岛了。
class Solution { public: int numIslands(vector<vector<char>>& grid) { if (grid.empty()) return 0; int count = 0; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { if (grid[i][j] == '1') { count++; dfs(grid, i, j); } } } return count; } void dfs(vector<vector<char>>& grid, int x, int y) { if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size()) return; if (grid[x][y] != '1') return; grid[x][y] = '0'; dfs(grid, x + 1, y); dfs(grid, x - 1, y); dfs(grid, x, y + 1); dfs(grid, x, y - 1); } };很多人在写这道题时容易把“寻找起点”和“扩散”混在一起。其实分层很清楚：主函数负责全图扫描，找到种子点；递归函数负责从种子点开始感染整个连通块。这个分层思路在处理“统计连通块个数”的问题时一定要刻在脑子里。
3.3 经典题三：被围绕的区域（LeetCode 130）
这道题比前两题多绕一步，很考验对 floodfill 的理解程度。题目要求：把矩阵中被'X'包围的'O'全部改成'X'，但边界上的'O'以及与之相连的'O'不能被修改，因为它们没有被完全包围。
正向思路是找出所有被包围的 O，这需要判断一个 O 是否连通到边界，比较麻烦。反向思路只需要两遍 floodfill：
第一遍，从矩阵四条边界出发，把所有与边界相连的'O'标记成一个特殊字符（比如'#'），这些 O 是“安全”的，不能改。
第二遍，遍历整个矩阵，凡是遇到没有被标记的'O'，说明它没有连接到边界，会被包围，所以把它改成'X'；同时把标记过的安全'#'还原成'O'。
class Solution { public: void solve(vector<vector<char>>& board) { if (board.empty()) return; int m = board.size(), n = board[0].size(); // 从边界 floodfill 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); } 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] == '#') board[i][j] = 'O'; } } } void dfs(vector<vector<char>>& board, int x, int y) { if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) return; if (board[x][y] != 'O') return; board[x][y] = '#'; // 标记为安全 dfs(board, x + 1, y); dfs(board, x - 1, y); dfs(board, x, y + 1); dfs(board, x, y - 1); } };这个“反向标记”的思路值得多琢磨几遍。以后再遇到“找符合 A 条件的区域，但不包括符合 B 条件的区域”这类问题，可以想想能不能从边界入口反向遍历，常常比正面硬刚简单得多。
3.4 复杂度分析：为什么 floodfill 是 O(mn)
很多同学写完代码会被问复杂度。floodfill 的时间复杂度是 O(mn)，因为每个格子最多被访问一次。这里的“最多”很关键：从起点开始，漫灌扩散不会回头，访问过的格子被标记之后就不会再进入。所以整个 DFS 过程遍历的节点总数，不会超过网格中连通区域的大小。最坏情况下全部连成一片，就是 m*n 个格子。
空间复杂度主要是递归调用栈的深度。最坏情况是一条“蛇形”通路贯穿整个网格，递归深度也能达到 m*n，所以空间复杂度最坏是 O(mn)。在面试中，这个最坏情况会被追问，你能答出来并且主动提出“可以用迭代栈或 BFS 来避免栈溢出”，会是一个加分点。
4. 常见问题与排查技巧实录
4.1 递归爆栈：大网格下 Stack Overflow
floodfill 最常见的实战翻车点就是递归深度过大。本地测小样例毫无问题，一上到 1000x1000 的全 1 网格，直接栈溢出。这不是算法错了，而是系统栈承载不住这么深的递归。
应对办法有两个。第一，换成显式栈模拟 DFS。自己维护一个stack（或 vector 当栈用），每次弹出栈顶元素，处理完再把未访问的邻居压栈。第二，直接换 BFS，用队列同样能完成 floodfill。下面给一个显式栈的模板：
void dfsIterative(vector<vector<int>>& grid, int startX, int startY, int oldColor, int newColor) { stack<pair<int, int>> st; st.push({startX, startY}); while (!st.empty()) { auto [x, y] = st.top(); st.pop(); if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size()) continue; if (grid[x][y] != oldColor) continue; grid[x][y] = newColor; st.push({x + 1, y}); st.push({x - 1, y}); st.push({x, y + 1}); st.push({x, y - 1}); } }这个写法把系统递归栈换成了堆上的显式栈，基本不会爆栈。代价是代码略长、需要管理栈的顺序。不过要注意，压栈顺序不同不会影响最终结果，只要保证四个方向都被检查即可。
4.2 死循环：标记顺序错了
我见过最多的 bug 是：递归函数内部先把当前格子颜色改了，但是忘了在递归前加标记；或者把“标记”放在递归调用之后。前者会导致已经染色的格子被再次当作合法扩散目标，后者会导致调用栈无限增长。
调试技巧很简单：打印递归进出的顺序。你可以在递归函数入口打印("enter", x, y)，出口打印("exit", x, y)。如果看到同样的坐标反复进出，八成是标记没第一时间生效。
4.3 边界范围和空矩阵处理
很多模板里直接写grid[0].size()，但如果grid是空的，这一步就直接越界了。所以主函数里往往要先判断if (grid.empty()) return;或if (grid.size() == 0 || grid[0].size() == 0)。这个细节看起来无关紧要，在 LeetCode 这类平台上就是一次 WA / RE 的差距。
另一个细节是：在某些语言里，二维数组的行数和列数可能分别获取，你写的grid[0].size()最好提前用一个变量缓存，否则在递归里反复调用还影响性能。
4.4 常见问题速查表
| 问题 | 原因 | 解决方案 |
|---|---|---|
| 递归栈溢出 | 网格过大、连通区域过长 | 改用显式栈或 BFS，或提前压缩网格 |
| 死循环、超时 | 没有及时标记已访问节点 | 进入递归后先标记，再扩散 |
| 结果少染/多染 | 方向数组不全，只覆盖右键和下移 | 检查 dx/dy 四方向覆盖完整性 |
| 数组越界 | 先访问 grid[x][y] 再判断 x、y 范围 | 把越界判断放递归函数第一行 |
| 输出没变化 | oldColor 等于 newColor | 主函数提前判断并返回 |
| 空矩阵崩溃 | 没检查行数或列数为 0 | 主函数开头判空 |
5. 扩展应用与通用套路总结
5.1 floodfill 不止在算法题里，也在工程代码里
这一类算法不只是刷题工具。图像处理里的区域填充、分割标注，游戏里的地图连通判断，扫地机器人的可达区域规划，甚至 Excel 里合并连续同色单元格，底层都有 floodfill 的影子。你在客户端开发里还可能遇到“手势识别连通域”“去除杂点”这类实际需求，算法题里练熟的手感可以直接迁移。
灰度图像二值化之后，floodfill 也可以用来筛选连通域：先按阈值把图像变成黑白，再用 DFS 把每个白色连通域找出来，计算面积，把面积小于阈值的区域去掉，就能实现简单的杂点清除。这个过程我在做图像预处理时经常用，直接把算法题模板搬过去稍加改动就够。
5.2 并查集是 floodfill 的另一个选择
如果你对数据结构熟悉，可能知道并查集也能做连通块统计。它和 DFS 的区别在于：DFS 适合“一次性找某个连通域”或“染色”，并查集适合“动态增加连接，随时查询两个点是否连通”的场景。如果题目需要对网格做多次合并操作，并查集更高效；如果只是简单的漫灌染色，DFS 模板无疑更直接。两者不是互斥的，比赛中常有题目两种做法都能过。
5.3 通用的 DFS floodfill 解题框架
写到最后，总结一套我每次做 floodfill 题都在脑子里过一遍的框架：
- 明确起点：题目给你坐标，还是需要全图扫描找种子点。
- 明确邻居范围：四方向还是八方向，横着走还是竖着走，能否斜线。
- 明确访问条件：什么状态的邻居允许进入。用式子写出来，别用嘴想。
- 明确终止条件：越界、不满足状态、已经访问过。
- 明确标记方式：原地改值还是 visited 数组。
- 动手写递归：判断 + 标记 + 递归。
六步走完，floodfill 的题基本就稳了。剩下的无非是题目包装成什么故事，是图像、岛屿、棋盘，还是迷宫。代码永远是这个骨架。
我个人在实际操作中的体会是：floodfill 类题目是最能体现“套路化思维”的一类题，它只要你把模板吃透、把边界情况照顾周全，剩下的就是修改状态判断条件。多刷几道变体题之后，你会发现自己看到“连通”“相邻”“感染”“扩散”这些词，脑子里自动就会弹出这套 DFS 框架。这种条件反射式的熟练，就是刷算法题最想要的收获。
