刷题刷到“递归、搜索与回溯”这一节几乎每个人都会被FloodFill算法绊一下。我也一样。二叉树上的DFS写得好好的一到网格题就发现不对劲——上下左右四个方向还有个二维数组要去重稍不注意就死循环、越界、重复计数。也就是从那时候起我才真正把“递归”从树形结构里解放出来开始理解搜索的通用形态。FloodFill算法简单说就是从一个起点出发把所有“相邻且满足条件”的位置都找到并标记像洪水漫灌一样把一整片连通区域都覆盖掉。这个算法本身不难难的是它在不同题目里的变体——图像渲染、岛屿数量、岛屿最大面积、被围绕的区域、太平洋大西洋水流问题、扫雷游戏、衣橱整理这些题刷一遍下来你对DFS的理解会有质的提升。这篇博文我把这七道题放在一起拆解从模板到变式从正向搜索到反向思维把每一步为什么这么做讲清楚。适合正在刷LeetCode、准备面试、或者刚刚开始接触DFS的读者也适合那些“能看懂题解但自己写就卡壳”的人。1. FloodFill算法的核心思路洪水从哪儿漫出来就往哪儿走1.1 从“油漆桶”到代码FloodFill到底是什么用过Windows画图或者Photoshop的人一定见过那个油漆桶工具——选一种颜色点一下图片里的某个区域整个连通的同色区域就全被填充成新颜色了。这个功能背后的算法叫FloodFill直译就是“洪水填充”。为什么叫洪水想象一下你往一块地形里倒水水会顺着地理上连通的低洼地带蔓延能流到哪里就湿到哪里。FloodFill算法就是这个过程从某个起点出发找到所有和它相邻、并且满足条件的位置一路扩散下去直到没有新的位置可走为止。放到算法题里这个“满足条件”具体指什么就是每题唯一的变量。图像渲染里条件是“与起点颜色相同”岛屿数量里条件是“是陆地”衣橱整理里条件是“数位和小于等于K”。条件在变但搜索的骨架完全一样。这也解释了为什么FloodFill是一个很好的算法学习主题它不是一道题而是一类题型的母题掌握了它的模板后续所有变体都是在模板上加加减减。1.2 为什么递归天然适合FloodFillFloodFill的过程天然具有递归特征到达一个位置之后我需要面对的问题和之前一模一样——检查这个位置是不是符合条件然后继续往四个方向走。这是典型的“大问题分解为同构子问题”的场景而递归正是描述这种行为的自然工具。你去看递归三要素函数定义、终止条件、单层逻辑。放在FloodFill这个场景里函数定义dfs(x, y)表示处理坐标为(x, y)的格子终止条件坐标越界、或者当前格子不需要处理单层逻辑标记当前格子然后递归处理上下左右四个格子。每次递归问题规模都会向边界推进递归终止条件保证不会无限递归。这个结构比显式维护一个栈去模拟扩散要清晰得多代码也短所以绝大多数题解都选择递归写法。当然递归有它的代价——系统栈深度有限当搜索范围特别大时可能栈溢出。这一点我在后面“常见问题”里会专门讲。不过对面试和大部分算法题来说递归写法依然是FloodFill的首选。2. 通用模板手写一个能跑的FloodFill2.1 详解DFS递归版模板我不想一上来就丢一堆代码让你背先把这个模板从逻辑上过一遍。以最经典的“图像渲染”LeetCode 733为例题目要求把起点所在的同色区域全部染成新颜色。核心代码长这样void dfs(vectorvectorint image, int x, int y, int oldColor, int newColor) { // 终止条件1越界 if (x 0 || x image.size() || y 0 || y image[0].size()) return; // 终止条件2不是要染的颜色或者已经染过 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会怎样递归会无限进行下去。因为当前格子被染成新颜色后它依然满足image[x][y] oldColor下一层递归又进来了永远走不到终止条件。所以很多写法会在入口处加一行if (newColor oldColor) return;当然如果你在DFS内部使用了额外的visited数组来标记是否访问过这个问题也能规避。但面试中更常见的做法就是利用原数组本身去重所以这个判断必不可少。这个细节我会在后面“常见问题”里再强调一次因为真的太容易踩了。2.2 方向数组与去重标记两个最容易被忽视的细节第一是方向数组。你当然可以在递归里写四次dfs调用就像上面那样当方向少的时候没毛病。但一旦题目变成八方向或者需要在多个函数里复用方向逻辑硬编码就会变得很啰嗦。推荐一开始就用方向数组int dir[4][2] { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };然后在dfs里循环for (int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; dfs(image, nx, ny, oldColor, newColor); }方向数组的好处是后续要增加方向斜对角或修改移动规则只改这一行就行。而且用一个循环统一处理四个方向逻辑更清晰也不容易像手写四遍dfs那样漏写一个。第二是去重标记。FloodFill里最大的风险是“走回头路”。比如从(0,0)往右走到(0,1)再从(0,1)往左走回(0,0)如果没有任何机制阻止这次访问两个格子会互相进入对方直到栈溢出。去重有三种常见手段直接修改原数组最适合岛屿类题目、用额外的visited二维数组适合不想破坏输入数据的情况、用特殊值标记比如被围绕的区域里临时改成A。多数FloodFill题目直接修改原数组就行因为最终的结果恰好就是要修改后的数组。保持思路统一不用为了“优雅”额外引入复杂度。2.3 BFS与DFS怎么选FloodFill用DFS和用BFS都能实现区别只在遍历顺序和空间占用上。DFS走的是“一条路走到黑”用一个递归栈做隐式存储代码短但在极端情况下比如整个地图是一大块连通区域递归深度可能很大BFS则是“一圈一圈往外扩散”用显式队列存储待访问节点没有递归深度问题代码稍微长一点。实战里怎么选我的习惯是棋盘大小在几百乘几百以内DFS写起来最快优先用DFS如果题目给的图可能特别大或者你担心递归栈爆掉就改用BFS。比如LeetCode 200岛屿数量用DFS没问题但如果你把grid扩大到一个超大二维数组DFS递归深度到几千层就可能出问题。这时候BFS更稳。void bfs(vectorvectorchar grid, int x, int y) { queuepairint, int q; q.push({x, y}); grid[x][y] 0; while (!q.empty()) { auto [cx, cy] q.front(); q.pop(); for (int i 0; i 4; i) { int nx cx dir[i][0]; int ny cy dir[i][1]; if (nx 0 || nx grid.size() || ny 0 || ny grid[0].size()) continue; if (grid[nx][ny] 1) { grid[nx][ny] 0; q.push({nx, ny}); } } } }这里有个细节入队前就把格子标记为访问过了而不是出队时再标记。如果你在出队时才标记同一个格子可能被多个邻居重复入队队列里会出现大量重复元素。这个坑我踩过一次队列越来越大内存直接爆掉。3. 七道经典题目逐题拆解从模板到变式的进阶之路3.1 图像渲染LeetCode 733新颜色等于旧颜色的坑这是最简单的FloodFill入门题题目描述就是“油漆桶”把跟起点连通且颜色相同的区域全部改成新颜色。代码我在2.1节已经给出来了这里只说三个容易出问题的点。第一还是那句老话如果新颜色和旧颜色相同直接返回原数组。这是LeetCode自己埋的测试用例很多人在这一步栽过。第二判断条件不要惯性写成if (image[x][y] newColor) return;。这样在第一次进入时可能没问题但递归展开后潜在逻辑会乱。明确用oldColor和newColor分开判断可读性更好。第三这道题的返回类型是vectorvectorint要直接修改原数组并返回引用。不要想着复制一份再改完全没必要空间复杂度徒增。图像渲染的价值在于它是所有FloodFill题里唯一一道完全不带“干扰逻辑”的题。你把这道题做透基本上DFS模板的框架就立住了后面的题都是在它的基础上加条件、加逆向、加规则。3.2 岛屿数量LeetCode 200一次FloodFill就是一座岛岛屿数量问的是1陆地有多少个连通块。核心思路特别有代表性遍历整个网格遇到一块没有标记过的陆地就执行一次FloodFill把整座岛全部标记为“已访问”计数器加一。关键在于这道题里我们直接修改原数组把访问过的陆地grid[i][j]从1改成0。为什么要这样做因为一旦把某块陆地纳入当前这座岛它就不会再属于任何其他岛屿了标记成水域既省去了额外的visited数组又天然防止重复访问。class Solution { public: int numIslands(vectorvectorchar grid) { 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(vectorvectorchar 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); } };你注意主函数的循环它其实做了两件事一是找“起点”二是启动FloodFill。这个模式在后续很多题目里都会复用——FloodFill不一定要从指定的起点开始有时候需要遍历所有位置每个位置都可能成为一次FloodFill的起点。这道题的时间复杂度是O(mn)因为每个格子最多被访问一次空间复杂度最坏是O(mn)对应递归栈的深度。这个复杂度分析是面试里常问的建议自己推一遍。3.3 岛屿的最大面积LeetCode 695让递归返回计数岛屿最大面积是岛屿数量的“进阶版”不仅要数连通块个数还要统计每个连通块里有多少个格子取最大值。思路是把dfs的返回值从void改成int每个格子返回“1 四个方向返回的面积之和”。当前格子面积为1加上能扩散到的所有格子的面积总和就是整个岛的面积。int dfs(vectorvectorint grid, int x, int y) { if (x 0 || x grid.size() || y 0 || y grid[0].size()) return 0; if (grid[x][y] ! 1) return 0; grid[x][y] 0; int area 1; area dfs(grid, x 1, y); area dfs(grid, x - 1, y); area dfs(grid, x, y 1); area dfs(grid, x, y - 1); return area; }主函数里对每个格子调用dfs维护一个maxArea就完事了。这道题特别值得做的原因是它让你理解“递归的返回值如何向上传递”。很多新手初学递归时只会在递归里做操作不知道返回值还能做累加这道题就是把“后序遍历”的思想从二叉树迁移到了网格上。本质上每个格子都像一个二叉树节点只不过不是两个子节点而是四个。你还可以试试用BFS去实现同样的统计逻辑在队列弹出的过程中计数。两种写法各来一遍之后这个系列的核心就不再有盲区了。3.4 被围绕的区域LeetCode 130把“判断被围绕”变成“找不被围绕的”这道题是FloofFill思维的第一个大拐弯也是我当年卡最久的一题。题目要求把所有被X围绕的O改成X但边界上的O不会被围绕因为它们的邻居会有网格外的部分所以全图最外圈任何与边界O连通的O都不该被改。如果你按照题目字面意思去判断每个O是不是被X包围会非常绕——你得检查四个方向是不是都堵死了。但实际上从边界的O出发做FloodFill把所有能走到的O找出来剩下的O就一定是被围绕的。具体步骤先遍历四条边界对所有边界的O执行DFS把连通的O临时标记成另一个字符比如A再遍历整个棋盘遇到A的说明它和边界连通恢复成O遇到原来的O说明它是被围绕的改成X。这个“临时标记”的思路很妙吧它能让你不额外开visited数组直接在原数组上做三态标记O是未处理的水X是石头A是和边界连通的水。class Solution { public: void solve(vectorvectorchar board) { int m board.size(), n board[0].size(); for (int i 0; i m; i) { dfs(board, i, 0); dfs(board, i, n - 1); } for (int j 0; j n; j) { dfs(board, 0, j); dfs(board, m - 1, j); } for (int i 0; i m; i) { for (int j 0; j n; j) { if (board[i][j] A) board[i][j] O; else if (board[i][j] O) board[i][j] X; } } } void dfs(vectorvectorchar 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] A; dfs(board, x 1, y); dfs(board, x - 1, y); dfs(board, x, y 1); dfs(board, x, y - 1); } };做这道题最大的启发是有些问题正向解决很复杂反向思考反而简单。“不被围绕”远比“被围绕”好判断那我们就先处理简单的部分剩下的自然就是难处理的。这种逆向思维在算法题里非常值钱。3.5 太平洋大西洋水流问题LeetCode 417反向DFS与二维标记数组这道题的思维复杂度又上了一个台阶也是这个系列里我觉得最能锻炼搜索思维的题目。题目给了一个m x n矩阵每个位置代表一个高度。左上角接太平洋右下角接大西洋。水从高处往低处流可以等于当前高度问哪些位置的水既能流到太平洋又能流到大西洋。如果正着思考从每个格子出发DFS判断能不能到达两个洋那每个格子都要做一次全图搜索复杂度直接爆炸。正确思路是反着来从四条边界出发逆着水流方向搜索。什么意思既然水能从高处流到低处那我们反过来想——从海边出发往高处和同高度走能走到的地方说明那里能流到海里。所以维护两个标记数组canPac[i][j]和canAtl[i][j]分别表示这个格子能不能流到太平洋和大西洋。从左上边界太平洋一侧DFS填充canPac从右下边界大西洋一侧DFS填充canAtl。最后遍历所有格子两个标记都为true的就是答案。class Solution { public: vectorvectorint pacificAtlantic(vectorvectorint heights) { int m heights.size(), n heights[0].size(); vectorvectorbool canPac(m, vectorbool(n, false)); vectorvectorbool canAtl(m, vectorbool(n, false)); for (int i 0; i m; i) { dfs(heights, canPac, i, 0); dfs(heights, canAtl, i, n - 1); } for (int j 0; j n; j) { dfs(heights, canPac, 0, j); dfs(heights, canAtl, m - 1, j); } vectorvectorint res; for (int i 0; i m; i) for (int j 0; j n; j) if (canPac[i][j] canAtl[i][j]) res.push_back({i, j}); return res; } void dfs(vectorvectorint heights, vectorvectorbool vis, int x, int y) { if (vis[x][y]) return; vis[x][y] true; int dir[4][2] { {1,0}, {-1,0}, {0,1}, {0,-1} }; for (int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; if (nx 0 || nx heights.size() || ny 0 || ny heights[0].size()) continue; if (heights[nx][ny] heights[x][y]) { dfs(heights, vis, nx, ny); } } } };这道题和“被围绕的区域”一样都是“反向”的代表作。区别在于前者用临时标记在原数组上操作后者因为需要同时维护两个洋的连通性所以用两个额外的二维bool数组。你可以看到FloodFill在不同场景下会有不同的“标记方案”这也是这类题灵活的地方。3.6 扫雷游戏LeetCode 529模板之外还要读懂游戏规则扫雷游戏是FloodFill系列里有意思的一道它把游戏规则直接塞进了算法里非常贴近真实场景。题目的规则可以拆成三个分支点击到地雷直接改成X游戏结束点击到的格子周围有地雷改成对应的数字不再扩散点击到的格子周围没有地雷改成B空白然后对周围八个方向的格子递归执行相同逻辑。也就是说这道题是“八方向”FloodFill并且增加了“统计周围地雷数”这一步。统计八个方向的地雷数是个固定动作值得单独抽出来写int countMine(vectorvectorchar board, int x, int y) { int cnt 0; for (int i -1; i 1; i) { for (int j -1; j 1; j) { if (i 0 j 0) continue; int nx x i, ny y j; if (nx 0 || nx board.size() || ny 0 || ny board[0].size()) continue; if (board[nx][ny] M) cnt; } } return cnt; }然后dfs里只需要根据是否挖到雷、雷数是否为0决定后续行为。这道题最需要提醒的是不要忘了已经挖开的格子会被置为B这个操作本身也起到了去重的作用所以递归里不需要额外的visited数组。如果忘记了你会在同一个空白格子上反复DFS最后还是栈溢出。我还想强调一点这道题很多人的代码差得不多但就是过不了原因往往是“只有countMine检查八个方向”但展开下层递归时用错了方向集合。务必统一——既然规则是八方向扩散那格子周围的八个格子都要判不能一边统计八方向一边扩散只有四方向那样漏掉雷数0但斜对角有雷的情况。3.7 衣橱整理LeetCode LCR 130 / 剑指Offer 13网格上的可达区域统计最后一道题是“衣橱整理”它出现在这个系列里有点隐晦但本质依然是FloodFill。题目大意是机器人从(0,0)出发每次只能移动到行坐标和列坐标的数位之和小于等于K的格子问最多能到达多少个格子。先要把“数位和”解释清楚。比如格子(35, 28)数位和就是352818。机器人可以上下左右移动但不能进入数位和大于K的格子。这道题的核心还是FloodFill但多了一个“准入条件”——数位和。int getSum(int x) { int sum 0; while (x) { sum x % 10; x / 10; } return sum; }主函数里从(0,0)开始DFS每进入一个格子就计数。因为你只能从(0,0)出发所以只需要调用一次dfs。去重可以继续用visited数组因为这里不能直接修改一个用来计算的数位值最好额外开bool数组。class Solution { public: int wardrobeFinishing(int m, int n, int cnt) { vectorvectorbool vis(m, vectorbool(n, false)); dfs(m, n, cnt, 0, 0, vis); return area; } void dfs(int m, int n, int k, int x, int y, vectorvectorbool vis) { if (x 0 || x m || y 0 || y n) return; if (vis[x][y]) return; if (getSum(x) getSum(y) k) return; vis[x][y] true; area; dfs(m, n, k, x 1, y, vis); dfs(m, n, k, x - 1, y, vis); dfs(m, n, k, x, y 1, vis); dfs(m, n, k, x, y - 1, vis); } private: int area 0; };这里我想专门说一个常见的面试追问为什么这道题只用向右和向下搜索也可以因为机器人从起点(0,0)出发在正常的上下左右移动规则下向左或向上的格子必然已经被从另一个路径访问过了。但为了保险起见面试里还是建议写全四个方向然后给面试官解释“这里上下左右都可以但实际只有向右和向下会带来新格子”。能讲清楚这一层说明你真的理解了这个算法的可达性本质而不是背着模板写的。4. 回溯的分界线FloodFill什么时候不需要恢复现场刷了上面这些题之后你可能会产生一个疑问不是说这个专题叫“递归、搜索与回溯”吗为什么这些题里一个“回溯”的影子都看不到其实这是因为FloodFill系列通常不需要恢复现场。回溯的核心动作是“恢复现场”——在递归返回前把之前修改过的状态改回去这样才能让其他分支有机会使用相同的资源。全排列、组合、N皇后这类题目需要回溯因为每条路径是独立的你在这条路径上占用的选择要在离开时释放。但FloodFill不一样。在“岛屿数量”里一旦把某个1改成0这块陆地的使命就结束了——它已经被计入这座岛后续任何其他搜索都不该再访问它。在“图像渲染”里格子染成新颜色后也不会再改变。它们的目标是标记一片区域而不是枚举所有可能路径。什么时候需要恢复我举个对比例子如果你在网格里找一条从起点到终点的路径并且允许走回头路。假设你能走过的格子标记为已访问如果不恢复现场第二条备选路径可能就找不到这时候就需要回溯在递归返回后把标记清除。所以是否需要回溯取决于同一个格子是否会被多条路径共享。这个区分想明白之后你再去看递归搜索回溯专题里的题目就不会再混淆“标记”和“回溯”的适用场景了。这也是我刷完这套题后最大的心得之一。5. 高频踩坑与排查实录5.1 栈溢出递归太深怎么办FloodFill用递归实现时最经典的问题就是栈溢出。力扣题目给出的矩阵尺寸通常不会为难你但如果你自己写测试用例时搞一个2000x2000的全是1的地图递归深度可能是几万层不溢出才怪。解决办法有三个改用BFS用显式队列替代系统栈手写显式栈模拟DFS可控性更好但代码量上去了如果是本地竞赛环境牛客、ACM可以使用编译器扩展扩大栈空间。我个人的建议是面试手写代码优先DFS因为短且易解释刷题时如果遇到大数据或超时就果断切BFS不必跟递归深度较劲。5.2 忘了标记导致死循环这是新手最常见的问题没有之一。在“岛屿数量”里忘了把grid[i][j]改成0在“太平洋大西洋水流问题”里忘了给visited数组打标记都会导致同一个格子被反复进入递归无限嵌套。我自己调试这类问题时有个习惯先在最外面主函数的循环里打印当前坐标看是不是在重复访问同一个点。如果是那十有八九是标记问题。标记操作一定要放在“进入格子”时立刻做放在递归调用之后往往就晚了——除非你有意延迟标记但FloodFill不需要这种技巧。5.3 越界判断的顺序越界判断必须放在数组访问之前。以下写法会直接崩溃if (grid[x][y] ! 1) return; // 错x可能越界 if (x 0 || x grid.size()) return;正确的顺序是先判断坐标合不合法再取数组值。虽然编译器不会提醒你但运行时数组越界会直接让程序崩掉。这属于路径依赖式的低级错误但也是面试现场最容易出现的尴尬。5.4 方向数组与递归的配合细节方向数组的顺序不会影响最终结果但在某些题目里会影响遍历顺序从而影响你调试时的输出。比如“岛屿数量”里先右后左还是先下后上打印出来的遍历路径完全不同。如果你需要对着结果调试建议方向顺序固定下来例如上下左右四个方向固定写成{1,0},{-1,0},{0,1},{0,-1}。另外在递归里每次循环都重新定义方向数组是可以的但如果在循环外定义方向数组再在内部修改就要小心多线程场景下的状态污染。单线程递归里这个问题不大但养成习惯把状态尽量作为局部变量或函数参数传递。5.5 输入数组为空时的边界LeetCode很多题目不会给出空数组但你自己写测试用例时一定会遇到。主函数第一行最好加上if (grid.empty() || grid[0].empty()) return ...;这种判空保护。虽然面试官不一定专门考这个但一个健壮的解法总是更讨喜。5.6 注意函数签名与引用传递C里需要用引用的地方一定要用引用。常见错误是把vectorvectorint传成vectorvectorint导致每次递归都拷贝一整个二维数组时间和空间全部爆炸。这个错误在递归里尤其致命因为递归层数多每一层都在拷贝完整数组复杂度直接变成指数级。6. 刷题建议从这套题里建立DFS直觉6.1 把模板背下来再忘掉它如果你看到这里建议你先放下文章自己把第2节的模板默写一遍。默写完再按这个顺序刷题图像渲染 - 岛屿数量 - 岛屿的最大面积 - 被围绕的区域 - 太平洋大西洋水流问题 - 扫雷游戏 - 衣橱整理。这个顺序不是随便排的它从最基础的模板逐渐过渡到反向思维再过渡到场景模拟每一步的跳跃都在上一个题目能接受的范围内。一次跳到第5题肯定吃力但一级级上来每道题你都能感受到“又多了点什么”。刷的过程里记得总结这题是在哪个环节改变了模板是改了判断条件、改了标记方案、改了递归返回值还是改了搜索方向每道题写完后把改动点记在题号旁边这个总结比刷十道新题更有价值。6.2 这套题之后下一步可以刷什么把这七道题消化完你的DFS基础基本就稳了下一步可以往这几个方向延伸求最短路径类FloodFill只管“能不能走到”不管“几步走到”需要求步数时就要用BFS逐层扩散回溯类组合、排列、子集、单词搜索、N皇后它们和FloodFill的区别在于需要恢复现场图上搜索从网格抽象到真正的图结构比如邻接表、邻接矩阵上的DFS/BFS思想完全一致只是存储结构变了。我个人觉得递归搜索回溯这一整个专题如果非要选一个核心能力那就是“把二维空间的遍历模型熟练掌握”。这套FloodFill题就是练这个能力最直接的训练场。根据我自己的经验刷到后面你会发现代码写得越来越顺不是因为背的题多而是因为“从一个格子往外扩散”的直觉形成了。看到新题你能在脑海里快速把格子图描出来知道从哪里进、从哪里出、什么时候停。这个直觉恰恰是刷算法题最宝贵的东西。