1. 项目概述从“涂色”到“连通域”的算法思维如果你用过Windows自带的“画图”工具一定对那个油漆桶图标不陌生。点一下一片封闭区域就被新颜色填满了。这个看似简单的功能背后站着的就是“洪水填充”算法。在算法竞赛和面试里它有一个更学术的名字Flood Fill。本质上它解决的是在一个矩阵或图中找出所有与起点“连通”且满足某种条件的点并对它们进行统一操作的问题。这不仅仅是给图片换颜色。在LeetCode上你会发现“岛屿数量”、“被围绕的区域”、“图像渲染”这些经典题目内核都是洪水填充。它考察的是你对深度优先搜索DFS或广度优先搜索BFS在二维网格上应用的熟练度以及对“连通性”定义的把握四方向还是八方向。很多朋友学DFS/BFS都是从树或图开始一到二维网格就发懵坐标转换、边界判断总是出错。今天我们就用C结合几道LC经典题把洪水填充从原理到实现再到避坑技巧彻底讲透。我的目标是让你看完后能闭着眼睛写出健壮的洪水填充代码并一眼看穿哪些题目是它的“变装秀”。2. 洪水填充的核心原理与DFS实现选择2.1 算法思想拆解它到底在“填”什么洪水填充算法的核心思想可以概括为以某个点为起点向四周通常为上下左右四个方向扩散将所有与起点“同属一个区域”的点找出来并标记或修改它们。这里的关键在于“同属一个区域”的定义在算法题中通常表现为值相同例如在LeetCode 733 “图像渲染”中将所有与起点像素颜色相同且相邻的像素点染成新颜色。满足特定条件例如在LeetCode 200 “岛屿数量”中将相邻的‘1’陆地视为一个岛屿我们需要找到所有连通的‘1’。这个过程像极了水滴在纸上晕染开或者洪水漫过平原因此得名。实现它的“引擎”就是DFS或BFS。今天我们先聚焦DFS。2.2 递归DFS vs 迭代DFS栈如何选择实现DFS有两种主流方式递归和用栈迭代。很多教程只讲递归因为它写起来简短。但在实战中尤其是面对大数据量的网格我们必须了解两者的优劣。递归DFS// 方向数组表示上下左右四个方向的坐标偏移 int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; void dfs(vectorvectorint image, int x, int y, int oldColor, int newColor) { // 边界检查 颜色判断 if (x 0 || x image.size() || y 0 || y image[0].size() || image[x][y] ! oldColor) { return; } // 染色 image[x][y] newColor; // 向四个方向递归探索 for (auto dir : dirs) { dfs(image, x dir[0], y dir[1], oldColor, newColor); } }注意递归深度受系统栈空间限制。对于一个1000x1000全连通的区域递归深度可能达到百万级极易导致栈溢出Stack Overflow。这是递归解法的致命弱点。迭代DFS栈void dfs_stack(vectorvectorint image, int sr, int sc, int newColor) { int oldColor image[sr][sc]; if (oldColor newColor) return; // 重要新旧颜色相同则直接返回避免死循环 stackpairint, int stk; stk.push({sr, sc}); while (!stk.empty()) { auto [x, y] stk.top(); stk.pop(); // 需要在出栈时再次检查因为同一个点可能被不同邻居重复入栈 if (image[x][y] ! oldColor) continue; image[x][y] newColor; // 将四个方向的邻居入栈 if (x - 1 0 image[x-1][y] oldColor) stk.push({x-1, y}); if (x 1 image.size() image[x1][y] oldColor) stk.push({x1, y}); if (y - 1 0 image[x][y-1] oldColor) stk.push({x, y-1}); if (y 1 image[0].size() image[x][y1] oldColor) stk.push({x, y1}); } }实操心得迭代栈实现没有递归深度限制更安全。但请注意我们在将邻居入栈前就进行了条件判断颜色和边界这比在出栈时统一判断效率更高减少了无效入栈。同时开头对oldColor newColor的判断至关重要否则会导致无限循环不断将自己和邻居入栈出栈。选择建议在面试或竞赛中如果明确知道数据范围很小比如网格不超过50x50用递归写法快且直观。否则一律优先使用迭代栈实现这是更工程化、更稳健的做法。我们后续的讲解也将以迭代栈为主。3. 经典习题精讲从“图像渲染”到“岛屿的周长”让我们把理论付诸实践用几道LeetCode经典题来深化理解。我会先给出问题描述和解题思路然后提供C迭代栈的实现代码并穿插关键注意事项。3.1 LC 733. 图像渲染 (Flood Fill)题目简述给你一个二维整数矩阵image表示一幅数字图像以及一个起点(sr, sc)和新颜色newColor。你需要从起点开始对图像进行“洪水填充”将所有与起点颜色相同且通过上下左右四个方向相连的像素点染成新颜色。思路解析这就是最标准的洪水填充问题。直接套用上面的迭代栈模板即可。唯一需要小心的是新旧颜色可能相同的特殊情况如果相同则无需任何操作直接返回原图否则会陷入死循环。C 实现class Solution { public: vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int newColor) { int oldColor image[sr][sc]; if (oldColor newColor) return image; // 关键特判 int m image.size(), n image[0].size(); stackpairint, int stk; stk.push({sr, sc}); while (!stk.empty()) { auto [x, y] stk.top(); stk.pop(); // 由于可能重复入栈出栈时需再次确认 if (image[x][y] ! oldColor) continue; image[x][y] newColor; // 四方向探索 if (x - 1 0 image[x-1][y] oldColor) stk.push({x-1, y}); if (x 1 m image[x1][y] oldColor) stk.push({x1, y}); if (y - 1 0 image[x][y-1] oldColor) stk.push({x, y-1}); if (y 1 n image[x][y1] oldColor) stk.push({x, y1}); } return image; } };避坑技巧注意代码中的两处检查。第一处是开头的oldColor newColor判断。第二处是出栈后的if (image[x][y] ! oldColor) continue;。为什么需要第二处想象一下点A的邻居是B和CB的邻居也是A和C。在遍历中A可能将B和C入栈B也可能将A和C入栈。这样点C就被重复入栈了两次。当第一次处理C时它被染色了第二次从栈中取出C时它的颜色已经变了不再是oldColor所以需要跳过避免无效操作和潜在错误。3.2 LC 200. 岛屿数量题目简述给你一个由1陆地和0水组成的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。思路解析我们可以遍历整个网格。当遇到一个1就说明发现了一个新的岛屿此时计数器加1。紧接着立即对这个1及其所有连通的1执行一次洪水填充将它们全部标记为已访问例如从1修改为0或一个特殊标记如2。这样后续遍历就不会再重复计数这些已经属于某个岛屿的陆地块了。C 实现class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); int islandCount 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { islandCount; // 使用栈进行DFS淹没这片岛屿 stackpairint, int stk; stk.push({i, j}); grid[i][j] 0; // 标记为已访问 while (!stk.empty()) { auto [x, y] stk.top(); stk.pop(); // 四方向探索 if (x - 1 0 grid[x-1][y] 1) { stk.push({x-1, y}); grid[x-1][y] 0; // 入栈时即标记避免重复入栈 } if (x 1 m grid[x1][y] 1) { stk.push({x1, y}); grid[x1][y] 0; } if (y - 1 0 grid[x][y-1] 1) { stk.push({x, y-1}); grid[x][y-1] 0; } if (y 1 n grid[x][y1] 1) { stk.push({x, y1}); grid[x][y1] 0; } } } } } return islandCount; } };性能优化点注意我在将邻居节点入栈的同时就立即将其标记为0。这是一个非常重要的优化。相比于在出栈时才标记这样做可以确保同一个1绝对不会被不同的邻居重复压入栈中。对于大规模网格这能显著减少栈的操作次数和内存占用。这是DFS迭代实现中一个经典的“访问即标记”技巧。3.3 LC 463. 岛屿的周长题目简述给定一个row x col的二维网格grid其中grid[i][j] 1表示陆地grid[i][j] 0表示水域。计算这个岛屿的周长假设只有一个岛屿。思路解析这道题可以不用完整的洪水填充但思维模式一脉相承。周长来源于哪里对于一块陆地格子它的每一条边如果相邻是水域或者超出边界那么这条边就是岛屿周长的一部分。因此我们可以遍历整个网格对每个陆地格子检查其四个方向。更“洪水填充”的思路是从任意一个陆地格子开始DFS/BFS在遍历过程中累加每个陆地格子对周长的贡献。C 实现DFS遍历累加法class Solution { public: int islandPerimeter(vectorvectorint grid) { int m grid.size(), n grid[0].size(); int perimeter 0; // 方向数组 int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { // 遍历当前陆地块的四个方向 for (auto dir : dirs) { int ni i dir[0]; int nj j dir[1]; // 如果相邻是水出界或值为0则这条边是周长 if (ni 0 || ni m || nj 0 || nj n || grid[ni][nj] 0) { perimeter; } } } } } return perimeter; } };思路延伸你也可以用真正的洪水填充来做找到一个起点陆地用栈或队列遍历整个岛屿。在遍历每个陆地格子时用同样的方法计算其四个方向对周长的贡献。这样做在只有一个岛屿时可能显得多此一举但其代码框架和“岛屿数量”题几乎一致能很好地锻炼举一反三的能力。核心在于理解洪水填充不仅是“染色”更是一种“连通域遍历”的范式在遍历过程中我们可以做任何事计数、修改、计算属性等。4. 洪水填充的变体与进阶技巧掌握了基础模型我们来看看一些变体和如何写出更鲁棒、高效的代码。4.1 八方向填充与连通性定义之前的例子都是四方向上、下、左、右连通。在某些图像处理场景中可能会要求八方向连通包括对角线方向。这只需要修改方向数组即可。四方向dirs [(-1,0), (1,0), (0,-1), (0,1)]八方向dirs [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]在算法题中务必仔细审题明确连通性的定义。例如“相邻”通常指四方向而如果题目说“周围”或没有明确说明则需要根据上下文判断或两者皆可时选择四方向因为更常用。4.2 使用“已访问”数组 vs 原地修改在“图像渲染”中我们直接修改了原图作为标记。在“岛屿数量”中我们把访问过的1改成0。这都是原地修改的方法节省空间。但在某些情况下我们不能或不想修改输入数据。这时就需要一个额外的visited二维布尔数组来记录哪些点已经被访问过。在将点入栈前除了检查颜色/值条件还要检查!visited[ni][nj]。vectorvectorbool visited(m, vectorbool(n, false)); stackpairint,int stk; stk.push({sr, sc}); visited[sr][sc] true; // 标记起点已访问 while (!stk.empty()) { auto [x, y] stk.top(); stk.pop(); // ... 处理当前点 ... for (auto dir : dirs) { int nx x dir[0], ny y dir[1]; if (nx0 nxm ny0 nyn !visited[nx][ny] image[nx][ny]oldColor) { stk.push({nx, ny}); visited[nx][ny] true; // 入栈即标记 } } }选择策略如果题目允许修改原数组且修改后不会影响后续逻辑比如只是染色那么原地修改是首选更简洁高效。如果输入数据需要保持原样或者修改原值会干扰判断例如原值可能有多种不能简单覆盖则必须使用visited数组。4.3 边界条件与输入检查的完备性健壮的洪水填充代码必须处理好各种边界情况起点坐标合法性在函数入口处应检查(sr, sc)是否在网格范围内。空输入处理如果输入的image或grid为空应直接返回。新旧颜色相等如前所述这是防止死循环的关键。栈/队列为空循环的终止条件。一个更健壮的模板开头如下vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int newColor) { // 1. 检查空输入 if (image.empty() || image[0].empty()) return image; int m image.size(), n image[0].size(); // 2. 检查起点合法性 if (sr 0 || sr m || sc 0 || sc n) return image; // 3. 检查是否需要填充 int oldColor image[sr][sc]; if (oldColor newColor) return image; // ... 开始填充 ... }5. 从DFS到BFS思路的拓展虽然本文聚焦DFS但必须提一下BFS。洪水填充用BFS队列实现同样简单且具有独特的性质。BFS实现框架队列void bfs(vectorvectorint image, int sr, int sc, int newColor) { int oldColor image[sr][sc]; if (oldColor newColor) return; int m image.size(), n image[0].size(); queuepairint, int q; q.push({sr, sc}); image[sr][sc] newColor; // 入队即标记 int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (auto dir : dirs) { int nx x dir[0], ny y dir[1]; if (nx 0 nx m ny 0 ny n image[nx][ny] oldColor) { q.push({nx, ny}); image[nx][ny] newColor; // 入队即标记 } } } }DFS栈 vs BFS队列的选择DFS栈实现上类似递归的思路探索路径会“一条路走到黑”再回溯。在空间上最坏情况如一条长蛇状区域栈的深度可能很大。BFS队列从起点一层层向外扩散。在求解“最短路径”或“最近距离”相关的问题时如找离起点最近的特定点BFS具有天然优势因为它按距离起点的层次进行遍历。对于洪水填充本身两者结果一样。个人经验在纯粹的连通域标记/染色问题上我更喜欢用栈实现的DFS代码和递归DFS思维接近且避免了递归深度问题。只有在问题本身带有“最短”、“最近”属性时才会优先考虑BFS。你可以把栈换成队列代码结构几乎不变这是非常美妙的。6. 实战中的高频错误与调试技巧即使理解了原理自己写的时候还是容易掉坑。这里总结几个我踩过的坑和调试方法。错误1忘记检查新旧颜色相同这是导致死循环的最常见原因。控制台会卡住或者程序超时。务必在函数开始处加上if (oldColor newColor) return ...;。错误2边界检查顺序错误在检查邻居时必须先检查坐标是否在网格范围内再访问数组。否则会出现数组越界访问导致运行时错误如Segmentation fault。// 错误写法先访问数组再检查索引 if (image[nx][ny] oldColor nx 0 nx m ny 0 ny n) // 如果nx越界第一句就崩溃了 // 正确写法先检查索引再访问数组 if (nx 0 nx m ny 0 ny n image[nx][ny] oldColor)C的逻辑运算符是短路求值的一旦nx 0为假后面的判断就不会执行保证了安全。错误3标记时机不当导致重复入栈/入队这是影响效率的关键。最佳实践是在节点入栈或入队的同时立即将其标记为已访问无论是修改原值还是设置visited数组。这能保证每个节点最多只被放入容器一次。如果等到出栈时才标记一个节点可能会被多个邻居重复放入容器造成大量冗余操作。调试技巧可视化打印对于小规模网格最有效的调试方法就是打印中间状态。在每次修改染色后或者每轮循环开始/结束时打印出当前的网格状态。你可以清晰地看到洪水是如何“蔓延”的在哪里卡住了或者为什么提前停止了。// 简单的打印函数 void printGrid(const vectorvectorint grid) { for (const auto row : grid) { for (int val : row) cout val ; cout endl; } cout ----- endl; } // 在DFS/BFS循环中关键位置调用 while (!stk.empty()) { // ... 处理 ... image[x][y] newColor; printGrid(image); // 观察染色过程 // ... 探索邻居 ... }7. 性能分析与进阶挑战对于面试你可能还需要分析算法的时间和空间复杂度。时间复杂度O(M * N)其中M和N是网格的行数和列数。在最坏情况下我们需要遍历网格中的每一个单元格一次。空间复杂度主要取决于栈或队列的最大长度。在最坏情况下例如整个网格都是需要填充的区域DFS栈或BFS队列可能同时存储O(M * N)个节点。但通常空间复杂度是O(min(M, N))吗不对对于DFS栈最坏情况可以是O(M*N)比如一个螺旋状路径。对于BFS队列最坏情况也是O(M*N)当起点在中心时。更严谨地说空间复杂度是O(M*N)。但在实际编程题分析中我们通常说“最坏情况需要存储所有节点”所以是O(M*N)。进阶挑战并行洪水填充对于超大规模图像如何利用多线程分割区域进行并行填充难点在于区域边界的合并。扫描线填充算法这是工业级图像软件如Photoshop真正使用的填充算法比简单的DFS/BFS高效得多。它按行扫描找到连续的线段进行填充能极大减少栈/队列的操作。有兴趣可以搜索“Scanline Flood Fill Algorithm”。处理非连通区域基础的洪水填充只能处理一个连通域。如果要把图中所有颜色为A但不一定连通的区域都染色就需要遍历整个图对每个未访问的A点启动一次填充。洪水填充是二维矩阵上DFS/BFS应用的“敲门砖”。彻底掌握它你就能轻松解决一大类“网格搜索”、“连通域”问题。核心就是定义好“连通”的条件选好DFS或BFS作为遍历工具处理好边界和重复访问然后在遍历过程中完成你的任务。多写几遍形成肌肉记忆下次再遇到矩阵里找岛屿、填颜色、算周长的问题你就能会心一笑知道这不过是洪水填充换了个皮肤而已。