1. FloodFill算法的本质从一个像素到一整片区域1.1 先搞懂什么是洪水填充很多刷题的朋友第一次见到FloodFill这个词是在图像处理软件里——比如Photoshop的油漆桶工具你点一个区域颜色就“蔓延”开来填满整个连通区。这个名字的由来很形象想象你在一个迷宫里倒水水会顺着所有能走的路流过去直到被墙壁挡住。算法做的事情和倒水完全一样从一个起点出发沿着相邻关系向四周扩散把所有满足条件的格子都标记或染色。放到算法题里它其实是一类问题的总称在二维矩阵或网格中从某个起点开始向上下左右四个方向有的题是八个方向做深度优先搜索DFS或广度优先搜索BFS把连通的、满足条件的格子全部处理一遍。这类问题表面上是“矩阵遍历”内核却是递归、搜索、回溯这三板斧的组合。FloodFill之所以重要是因为它几乎是所有图论搜索题目的最小原型。无论是岛屿类问题、着色类问题、迷宫类问题还是带约束条件的连通域统计底层都是同一套搜索框架。我刷了几十道这类题后最大的感受是把它当作一个“搜索模板”来背熟远比自己每次从零推导要高效得多。1.2 核心解题框架方向数组与边界检查任何FloodFill题目骨架都是固定的四件事方向数组定义“相邻”的含义。最常用的是上下左右四方向用两个数组表示int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1};有的题比如扫雷的点击展开还需要处理对角线那就是八方向int dx[8] {1, 1, 1, 0, 0, -1, -1, -1}; int dy[8] {1, 0, -1, 1, -1, 1, 0, -1};边界检查每次准备访问邻居之前先判断新坐标是否在矩阵范围内。这个判断必须放在访问数组下标之前否则轻则数组越界重则段错误。我习惯用一个isValid辅助函数bool isValid(int x, int y, int n, int m) { return x 0 x n y 0 y m; }访问标记为了防止同一个格子被重复访问必须用一个visited数组或直接在原矩阵上修改。这里有一个非常经典的坑标记的时机。我最初写DFS经常在递归返回之后才标记结果导致死循环后面单独用一节详细说。递归/迭代结构DFS用递归最简洁BFS用队列最直观。选哪种取决于题目对“搜索顺序”的要求和递归深度会不会爆栈。1.3 DFS与BFS的选型思维我知道很多人一看到FloodFill心里默认就是DFS因为代码短、好写。但实际面试和竞赛中选型是有讲究的DFS递归代码最短逻辑最贴合“洪水蔓延”的直觉。但缺点是递归栈的深度等于连通区域的面积如果矩阵很大比如1000×1000全是同一颜色递归深度可能达到百万级直接爆栈。面试时如果题目没有明确说矩阵规模我一般先写DFS同时心里清楚它可能栈溢出如果一看规模就是大矩阵立刻转BFS。BFS队列空间复杂度在极端情况下可能更高队列里存的是一层的节点但在网格类题目里通常不会超出O(n×m)。BFS还有一个天然优势它能天然地处理“多源”场景比如后面要讲的太平洋大西洋水流问题多源BFS就比DFS更好理解和实现。关于回溯FloodFill本身一般不涉及“恢复现场”。回溯的核心是“尝试-撤销-再尝试”适用于路径搜索、排列组合这类需要穷举所有可能的问题。FloodFill只是无脑向四周扩散不需要撤销所以真正的回溯题比如衣橱整理里的路径约束判断才会用到回溯技巧。这一点很多人混淆我后面会在衣橱整理题目里展开讲。2. 从单点到全局图像渲染、岛屿数量与最大面积2.1 图像渲染LeetCode 733最标准的FloodFill模板题目描述很简单给你一个二维数组image起点坐标(sr, sc)和一个新颜色newColor把起点所在的连通区域颜色与起点相同的格子全部改成新颜色。这道题没什么弯弯绕绕就是最纯粹的洪水填充。唯一要注意的是边界情况如果起点颜色本身就等于newColor直接返回原图否则会陷入死循环。为什么因为你在DFS里判断“颜色相等就改色”改完后又判断“颜色相等”就会无限递归下去。void dfs(vectorvectorint image, int x, int y, int oldColor, int newColor, int n, int m) { if (!isValid(x, y, n, m) || image[x][y] ! oldColor) return; image[x][y] newColor; for (int i 0; i 4; i) { dfs(image, x dx[i], y dy[i], oldColor, newColor, n, m); } } vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) { int n image.size(), m image[0].size(); int oldColor image[sr][sc]; if (oldColor color) return image; dfs(image, sr, sc, oldColor, color, n, m); return image; }这里我直接把image矩阵当作visited数组用改掉颜色就相当于标记了。很多题都可以这样“原地标记”省掉一个额外的visited矩阵空间复杂度从O(n×m)降到O(1)。但有个前提题目允许修改原数组。如果题目禁止修改就必须单独开一个visited数组比如下面岛屿数量这道题如果直接在原始grid上标记有可能影响后续判断需要谨慎。2.2 岛屿数量LeetCode 200从单个点到全图扫描图像渲染是“给你一个起点”而岛屿数量是“你需要自己找起点”。思路很直接遍历整个二维网格每遇到一个没访问过的1就把它当成一个新岛屿计数器加一然后对这个起点做一次FloodFill把整座岛屿全部标记为已访问之后就不会再重复计数了。void dfs(vectorvectorchar grid, int x, int y, int n, int m) { if (!isValid(x, y, n, m) || grid[x][y] ! 1) return; grid[x][y] 0; // 直接在原图上标记 for (int i 0; i 4; i) { dfs(grid, x dx[i], y dy[i], n, m); } } int numIslands(vectorvectorchar grid) { int n grid.size(), m grid[0].size(), count 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1) { count; dfs(grid, i, j, n, m); } } } return count; }我第一次做这道题时有个疑问为什么把grid[i][j]改成0不会影响到其他岛屿的判断后来想明白了因为每次FloodFill只处理当前连通的岛屿把它的所有格子都改成0其他岛屿的1不受影响。而且我们遍历到某个格子时如果它是0说明它要么本来就不是陆地要么已经被前面的岛屿处理过了不会重复计数。这道题还有一个变化如果题目不允许修改原数组那就需要一个visited矩阵。代码如下int numIslands(vectorvectorchar grid) { int n grid.size(), m grid[0].size(), count 0; vectorvectorbool visited(n, vectorbool(m, false)); for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1 !visited[i][j]) { count; dfs(grid, visited, i, j, n, m); } } } return count; }两种写法复杂度相同时间O(n×m)空间最坏O(n×m)但“原地修改”的版本在空间上更优面试时根据题目的限制条件灵活选。2.3 岛屿的最大面积LeetCode 695在连通过程中统计状态这道题和岛屿数量很像只不过要求的是最大面积。所谓面积就是一次FloodFill能访问到的格子总数。实现上就是在DFS的每次递归里累加并返回。int dfs(vectorvectorint grid, int x, int y, int n, int m) { if (!isValid(x, y, n, m) || grid[x][y] 0) return 0; grid[x][y] 0; // 标记已访问 int area 1; for (int i 0; i 4; i) { area dfs(grid, x dx[i], y dy[i], n, m); } return area; } int maxAreaOfIsland(vectorvectorint grid) { int n grid.size(), m grid[0].size(), ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1) { ans max(ans, dfs(grid, i, j, n, m)); } } } return ans; }这里有一个细节值得注意area的累加方式。每次递归返回的是“当前格子 四个方向的面积”方向之间用加号连接天然地把整个岛屿的面积算出来了。如果你不习惯递归返回值也可以用全局变量或者引用参数来统计void dfs(vectorvectorint grid, int x, int y, int n, int m, int area) { if (!isValid(x, y, n, m) || grid[x][y] 0) return; grid[x][y] 0; area; for (int i 0; i 4; i) { dfs(grid, x dx[i], y dy[i], n, m, area); } }两种方式我都用过返回值的方式更函数式引用参数的方式更直观。刷题时怎么顺手怎么来但面试时建议先想清楚哪种代码更不容易出错。关于这三个题目我建议按“模板→批量扫描→统计返回值”的顺序去理解它们是一个递进关系图像渲染是单点扩散岛屿数量是把扩散当作标记工具最大面积是在扩散中收集信息。递进关系理清了后面所有变体题都只是在这基础上加条件。3. 逆向思维与多源扩散被围绕的区域与太平洋大西洋水流问题3.1 被围绕的区域LeetCode 130从边界反向遍历题目要求把矩阵中被X完全包围的O改成X但边界上的O以及和边界O相连的O都不算被包围要保持原样。我第一次做这道题时正着想的思路是找到所有O的连通块检查每个连通块是否接触边界。这个思路可以但实现起来很繁琐需要判断每个连通块是否包含边界格子还要处理“先标记后判断”的顺序问题。后来我学到一个非常漂亮的逆向思路从边界出发把能和边界连通的O全部标记出来剩下的O自然就是被包围的。这样问题就变成了一个简单的从多个边界点出发的FloodFill。void dfs(vectorvectorchar board, int x, int y, int n, int m) { if (!isValid(x, y, n, m) || board[x][y] ! O) return; board[x][y] A; // 标记为“与边界连通” for (int i 0; i 4; i) { dfs(board, x dx[i], y dy[i], n, m); } } void solve(vectorvectorchar board) { int n board.size(), m board[0].size(); // 从四边界的O开始把所有边界连通块标记为A for (int i 0; i n; i) { if (board[i][0] O) dfs(board, i, 0, n, m); if (board[i][m-1] O) dfs(board, i, m-1, n, m); } for (int j 0; j m; j) { if (board[0][j] O) dfs(board, 0, j, n, m); if (board[n-1][j] O) dfs(board, n-1, j, n, m); } // 遍历整个矩阵A恢复为O其余O改为X for (int i 0; i n; i) { for (int j 0; j m; j) { if (board[i][j] O) board[i][j] X; else if (board[i][j] A) board[i][j] O; } } }这个逆向思维是算法题里非常经典的技巧正难则反。当正着判断“被包围”很复杂时反过来找“没被包围”的剩下的自然就是答案。我把这类题称为“染色法”用一个新的标记颜色把不符合条件的部分先“染色”隔离出来最后再统一处理。3.2 太平洋大西洋水流问题LeetCode 417多源DFS与结果的交集这道题是FloodFill系列里综合性较强的题目。题意大致是一个n×m矩阵表示海拔左上和右上的边界是太平洋右下的边界是大西洋题目定义不同版本略有差异以LeetCode 417为准左边界和上边界是太平洋右边界和下边界是大西洋。水从高处往低处流只能流到海拔不高于自己的格子要求返回所有“既能流到太平洋又能流到大西洋”的格子坐标。最朴素的想法对每个格子模拟水流复杂度O((n×m)^2)在矩阵为200×200时直接超时。正确的做法是用逆向思维从边界出发从低处往高处走不走回头路——即搜索时允许往“海拔不小于当前格子”的邻居扩展。这样从太平洋边界出发标记所有能到达的格子从大西洋边界出发标记所有能到达的格子两个标记的交集就是答案。void dfs(vectorvectorint heights, vectorvectorbool visited, int x, int y, int n, int m) { if (visited[x][y]) return; visited[x][y] true; for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (isValid(nx, ny, n, m) heights[nx][ny] heights[x][y]) { dfs(heights, visited, nx, ny, n, m); } } } vectorvectorint pacificAtlantic(vectorvectorint heights) { int n heights.size(), m heights[0].size(); vectorvectorbool pac(n, vectorbool(m, false)); vectorvectorbool atl(n, vectorbool(m, false)); // 太平洋左边界和上边界 for (int i 0; i n; i) dfs(heights, pac, i, 0, n, m); for (int j 0; j m; j) dfs(heights, pac, 0, j, n, m); // 大西洋右边界和下边界 for (int i 0; i n; i) dfs(heights, atl, i, m-1, n, m); for (int j 0; j m; j) dfs(heights, atl, n-1, j, n, m); // 取交集 vectorvectorint ans; for (int i 0; i n; i) { for (int j 0; j m; j) { if (pac[i][j] atl[i][j]) ans.push_back({i, j}); } } return ans; }这段代码里的核心变化是搜索条件从“”变成了“”方向从“往低处流”变成“往高处爬”。物理上虽然反了但逻辑上完全等价——水从边界能流到的地方就是边界能逆流回去的地方。我第一次做的时候疑惑为什么不需要visited去重之外的其他标记。后来想明白visited不仅用来防止重复访问还天然作为一个“可达集合”的结果容器。每个DFS跑完visited矩阵里为true的格子就是这一侧能到达的所有格子。这道题如果用BFS也能做反而更贴近“多源扩散”的形象先把所有边界点压入队列然后把它们当作一个整体向外扩展。BFS在多源场景下不需要写多个起点而是初始化时全部入队很自然。我在实际写题时多源DFS更常用因为代码量更少而且对递归深度有把握时性能足够。4. 综合模拟与回溯变体扫雷游戏与衣橱整理4.1 扫雷游戏LeetCode 529按点击状态分情况讨论扫雷游戏是FloodFill里少见的“强模拟”题。题目给一个字符矩阵M表示未挖出的地雷E表示未挖出的空地B表示已挖出的空白格数字字符1-8表示周围地雷数。点击一个格子需要根据规则更新矩阵。规则如果点中M直接改成X踩雷游戏结束。如果点中E且其周围八方向有地雷则改成数字不再递归。如果点中E且周围没有地雷则改成B并递归展开所有未挖出的相邻格子。这题本质上就是一个带条件的FloodFill只有“当前格子周围没有地雷”才继续扩散。关键是先数清楚当前格子周围的地雷数量根据数量决定是变成数字还是继续递归。void dfs(vectorvectorchar board, int x, int y, int n, int m) { if (!isValid(x, y, n, m) || board[x][y] ! E) return; int cnt 0; for (int i 0; i 8; i) { int nx x dx8[i], ny y dy8[i]; if (isValid(nx, ny, n, m) board[nx][ny] M) cnt; } if (cnt 0) { board[x][y] 0 cnt; // 周围有雷标数字不再扩散 } else { board[x][y] B; for (int i 0; i 8; i) { dfs(board, x dx8[i], y dy8[i], n, m); } } } vectorvectorchar updateBoard(vectorvectorchar board, vectorint click) { int x click[0], y click[1]; if (board[x][y] M) { board[x][y] X; // 踩雷 return board; } int n board.size(), m board[0].size(); dfs(board, x, y, n, m); return board; }这题有几个让我印象深刻的坑递归条件必须要求 board[x][y] E。如果不加这个条件你可能在扩展过程中重复访问已经变成B的格子无限递归。加了之后扩展时只会处理未挖出的空地。数字格子不再扩散。这是游戏逻辑的核心周围有地雷的格子只是显示数字起到“警示”作用不再展开。如果漏掉这个条件整个游戏变成了把整个矩阵全翻开的无脑填充。八方向遍历。扫雷的“相邻”是八个方向这和之前四方向的题不一样方向数组定义错就直接错了而且要特别注意不要越界。这道题整体上是对FloodFill的一次“加了约束”的练习不是所有满足颜色相等的格子都能扩散而是要满足“周围地雷数为零”这个额外条件。刷完这道题之后我对“FloodFill不只是同色扩散”有了更深的体会——它可以是任何满足特定预设条件的连通区域扩散。4.2 衣橱整理剑指Offer 13 / LeetCode LCP 类似题带约束的连通域搜索衣橱整理这道题我最初看到觉得和FloodFill八竿子打不着因为题目描述不是矩阵而是“若干件衣服”的整理方案。但很多题解把它归类到“搜索与回溯”是因为它本质上是一个DFS在状态空间里的遍历每件衣服可以被选择放进某一类不同选择组合成了搜索树需要回溯来穷举所有分配方案。不过如果面试官把“衣橱整理”当成一个二维网格问题来问——比如“给定一个衣橱的格子布局某些格子被占据了你需要从某个格子出发把所有可整理的衣服格子搜索出来”——那它和FloodFill就完全重合了。我遇到过类似这种变体矩阵中数字0表示空位数字1表示有衣物你需要把连通的、可以移动的衣物区域做标记。这就是一个标准的带约束FloodFill只对数字为1的格子扩散而且每走过一个格子要标记避免重复。这里的关键不是代码本身而是你对“搜索空间”的理解。衣橱整理更接近于一个回溯问题在状态空间里搜索合法整理路径每做一次选择就递归选择不合法就回溯换一条路。举个例子如果你有4件衣服需要按颜色红、蓝、白分类那么整理方案就是所有可能的颜色分配序列这是一个指数级的搜索树必须用回溯vectorstring colors {红, 蓝, 白}; vectorstring path; void backtrack(vectorstring clothes, int idx) { if (idx clothes.size()) { // 记录一种整理方案 return; } for (string color : colors) { path.push_back(color); // 尝试选择 backtrack(clothes, idx 1); path.pop_back(); // 撤销选择回到上一层 } }我个人在实际刷题中的体会是很多人把“搜索”和“回溯”混为一谈其实它们的区别很关键——搜索是遍历整个状态空间回溯是在搜索过程中“尝试→撤销”的递归技巧。FloodFill本身属于搜索不需要撤销而像衣橱整理这种“在多个选择中找方案”的题目才是回溯的用武之地。遇到一棵多分支的搜索树脑袋里要有“选了这个之后还能不能选别的”的意识这就是回溯。5. 高频坑点与调试心得如何一次写对FloodFill5.1 死循环与栈溢出访问标记的时机这是FloodFill系列里最严重的坑。很多新手写DFS时习惯这样写void dfs(vectorvectorint grid, int x, int y) { // 先处理当前格子 grid[x][y] 0; for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (isValid(nx, ny, n, m) grid[nx][ny] 1) { dfs(grid, nx, ny); } } }这个写法是正确的因为进入递归之前就标记了当前格子。但如果你换一种写法void dfs(vectorvectorint grid, int x, int y) { if (grid[x][y] ! 1) return; for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (isValid(nx, ny, n, m) grid[nx][ny] 1) { grid[nx][ny] 0; // 标记放在递归调用前 dfs(grid, nx, ny); } } }如果不先标记就调用dfs那么回到上一层时邻居又会被其他方向访问一遍形成“A访问B、B访问A”的无限递归直接栈溢出。正确做法是在进入递归的那一刻就完成标记不管是进入函数体后立刻标记还是在调用前标记二选一但绝不能在返回后标记。5.2 边界条件从0到n-1的细节矩阵题里最常见的崩溃原因就是数组越界。我写isValid函数时习惯把矩阵的行列数作为参数传进去这样最保险bool isValid(int x, int y, int n, int m) { return x 0 x n y 0 y m; }另外x对应的是行y对应的是列千万别弄混。我第一次写200题时在二维数组上把行和列搞反了导致访问grid[y][x]而不是grid[x][y]结果在特殊矩阵下直接越界。调试了半小时才发现问题从此我统一用x表示行、y表示列并在代码注释里标明。5.3 关于“是否需要回溯”的判断很多人在做DFS题目时会条件反射地问“要不要恢复现场”然后在FloodFill题里也尝试恢复导致代码又长又容易错。我的经验法则是如果题目要求的是“从起点出发把所有满足条件的格子都染色/标记”比如图像渲染、岛屿数量、被围绕的区域不需要回溯。如果题目要求的是“从起点出发找一条路径需要尝试不同的方向并回退”比如迷宫类、状态搜索类需要回溯。这里有一个特别容易迷惑的场景有些题目虽然看起来是“找连通区域”但要求的是“连通区域是否合法”且搜索顺序会影响结果这时候就需要回溯。被围绕的区域里如果不用逆向思路而是正着判断很容易写出需要回溯的版本用了逆向思路后反而完全不需要回溯。所以数据结构选择得当很多“需要回溯”的题可以转化为“单纯的FloodFill”。5.4 我在调试中形成的“三板斧”刷了大量FloodFill题之后我总结出了一个调试流程每次遇到新题都按这个顺序来先画图。拿纸笔或白板画一个小的5×5矩阵手动模拟一遍题目过程搞清楚“从哪个点开始”、“向哪些方向扩散”、“什么条件下可以扩散”。先写边界和主循环。把isValid和主循环遍历矩阵的for循环先写出来确保不越界、能遍历。再写核心递归。递归逻辑尽量保持最简只有“不满足条件就return标记四方向/八方向递归”这三件事。如果题目复杂比如扫雷我还会把“当前格子周围地雷数量”单独封装成一个函数方便测试时单独验证。调试的时候先用小数据样例验证再换随机生成的大矩阵做压力测试防止递归深度过深。5.5 从这7道题里提炼出的通用套路最后把这7道题放在一起看你会发现它们其实是同一个框架的不同变体题目起点搜索方向扩散条件是否回溯额外技巧图像渲染给定点四方向颜色等于旧值否原地标记岛屿数量全图扫描四方向等于1否遍历计数岛屿最大面积全图扫描四方向等于1否递归返回值被围绕的区域边界点四方向等于O否逆向染色太平洋大西洋水流两组边界四方向高度当前否多源交集扫雷游戏点击点八方向周围无雷否分情况模拟衣橱整理状态起点状态转移方案合法是回溯穷举我刷完这一串题后最强烈的感觉是核心模板一直没变变的是“你的搜索目标”和“你需要收集的信息”。图像渲染要的是“染色”岛屿数量要的是“计数”最大面积要的是“统计”被围绕的区域要的是“判断包含关系”水流要的是“多源可达”扫雷要的是“带条件的展开”衣橱整理要的是“方案枚举”。一旦你能从“套模板”升级到“看懂题目在问什么、需要收集什么信息”的层面这些题就不再是背题而是真正的思路训练。按照我个人的刷题经验建议的顺序是图像渲染→岛屿数量→岛屿最大面积→被围绕的区域→太平洋大西洋水流→扫雷游戏→衣橱整理。前面五道题可以帮你建立FloodFill的手感和逆向思维扫雷可以练兵分情况讨论衣橱整理则是在同一个搜索体系下引入回溯概念为更高难度的DFS题比如排列组合、N皇后打好铺垫。这套组合拳打下来至少对我而言效果比单刷几十道松散题目要好得多。