写这玩意儿之前，我其实犹豫了一下。网络上把Flood Fill（漫水法）单独拎出来讲的教程已经多到烂大街，讲最短路模型的更是堆成山。但把这两者放在一起，当成一个“组合技”来拆解的，还真不多见。不少朋友学算法有个误区，觉得Flood Fill就是图像处理里的油漆桶工具，或者顶多用来数数岛屿数量，跟最短路八竿子打不着。
但实际上，Flood Fill和最短路的结合，才是刷题和实战里最香的那块肉。我们常说的BFS最短路，本质上就是一种特殊的“漫水”过程——水从起点漫出去，每一层扩散的深度就是步数，当水漫到终点时，走过的路径天然就是最短路径。反过来说，如果你只会套BFS模板，而没想通它和Flood Fill底层逻辑的关联，遇到带权值、多起点、带状态约束的“变种漫水”问题，照样会卡死。
这篇文章，我想聊的正是这个交叉地带：既有纯Flood Fill的连通性染色，也有从漫水视角理解最短路模型的解题思路，还有两者结合后怎么处理多源扩散、01代价和状态压缩。不多废话，直接上核心。
1. 先把漫水法这件事彻底嚼碎
1.1 它到底在算什么
Flood Fill最朴素的描述是：从一个种子点出发，向它四周扩散，凡是“长得一样”或者“满足条件”的邻居，都划归到同一个集合里。这个操作在图形学里叫种子填充，在算法题里叫连通块染色，在网格里它就是“判断点和点之间的可达性”。
想抓住它的本质，别把它看成什么高深算法，就把自己想成一桶水。把水从一个格子里倒下去，水会因为重力向四周漫开，遇到墙就绕开，遇到低洼就积起来。等水彻底不流了，被水淹过的地方，就是那一个连通区域。整个过程不涉及最优路径的选择，它只关心“能不能到”，不关心“怎么到最划算”。
这一点特别关键。漫水法解决的是可达性集合问题，而最短路模型解决的是最优路径选择问题。很多人学的时候把两者割裂开，其实它们是同一个硬币的两面。当你把水漫出去时，假如给每次“漫一步”都记一个时间戳，那首次到达某个点的时间戳，就是从这个源点到该点的最短步数。
1.2 两种实现姿势：递归DFS和队列BFS
漫水法的标准实现有两条路。第一条是DFS递归，函数长这样：进入一个格子，标记已访问，然后向上下左右四个方向递归调用自身。代码写起来非常短，理解起来也直观，像感染一样往外扩散。
void dfs(int x, int y, int color) { if (x < 0 || x >= n || y < 0 || y >= m) return; // 出界就停 if (grid[x][y] != target || visited[x][y]) return; // 颜色不同或已访问就停 visited[x][y] = true; grid[x][y] = color; dfs(x - 1, y, color); dfs(x + 1, y, color); dfs(x, y - 1, color); dfs(x, y + 1, color); }另一条是BFS队列，借助一个先进先出的队列，从种子点开始，一层一层往外扫描。
void bfs(int sx, int sy, int color) { queue<pair<int, int>> q; q.push({sx, sy}); visited[sx][sy] = true; grid[sx][sy] = color; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (visited[nx][ny] || grid[nx][ny] != target) continue; visited[nx][ny] = true; grid[nx][ny] = color; q.push({nx, ny}); } } }1.3 为什么实战里我更推荐BFS
DFS漫水虽然写起来快，但在比赛和工程实战里，我几乎不主动选它。原因有三个。
第一，递归深度不可控。一个1000x1000的网格，如果全部连通，DFS递归深度可能达到一百万层。系统栈根本扛不住，爆栈几乎是必然的。虽然可以手写栈模拟递归，但代码量上去了，收益却不大。
第二，BFS天然自带层次信息。这一点是DFS完全比不上的。BFS的每一层循环代表向外扩散了一步，这意味着你在漫水的同时，其实已经顺带把所有点的最短距离算出来了。而DFS只保证“能访问到”，访问顺序和距离没有任何关系。
第三，BFS改成多源扩散极其顺手。只要初始化队列时把所有起点都丢进去，然后正常跑循环，就是一个标准的多源BFS。这个问题我们后面专门聊。
注意：如果题目给的网格特别稀疏、连通块很小，DFS的爆栈风险不高，日常自己写着玩无所谓。但一旦你打算上这个算法去打比赛或者去面试手撕，请默认无脑换BFS，省心。
2. 从漫水到最短路，这一步是怎么迈过去的
2.1 漫水法天生自带“距离感”
我用一个非常简单的例子帮大家建立直觉。
假设现在有一个0和1组成的网格，0是空地，1是墙。你站在(0,0)，想走到(2,2)，最少走几步？这个问题所有学过BFS的人都会做，但这套做法放到Flood Fill的语境下，其实就是从起点这个“种子”开始漫水。第一次扩散走一步能到的格子，第二次扩散走两步能到的格子。每个格子第一次被“淹没”的轮次，就是它距离起点的最短步数。
这就是为什么Flood Fill能和最短路模型无缝衔接：BFS本身既是连通性判断工具，也是无权图最短路求解器。你不需要额外开一个Dijkstra，因为每步代价都为1时，BFS的扩散顺序天然等价于按照距离递增的顺序扫描。
2.2 当代价不都是1时，模型开始升级
但是现实中没那么理想。网格里有的格子能走，有的格子走一步要代价，有的格子甚至能“瞬间移动”（代价为0或1）。这时候普通BFS就撑不住了，因为队列的先进先出顺序不再等价于距离递增的顺序。
这一步就是Flood Fill和“标准最短路模型”的分水岭。我一般把它分成两档。
第一档是01-BFS。如果每一步的代价只有0和1两种，比如有的地形是平地代价1，有的地形是传送门代价0，那么可以用双端队列Dijkstra的退化版——代价为0的转移从队头插入，代价为1的转移从队尾插入。这样依然能保证首次出队时距离一定是最短的，时间复杂度仍然是O(V+E)，比堆优化Dijkstra还快。
第二档是堆优化Dijkstra。如果代价的种类很多，比如这个格子要走3步，那个格子要走5步，那就必须把队列换成优先队列，每次取当前距离最小的节点扩展。这时候你就不能再把它叫“漫水”了，因为它不再是均匀扩散，而是沿着代价最省的路径“寻宝”。
2.3 多源扩散：所有起点同时漫水
多源BFS是Flood Fill与最短路结合最漂亮的点之一。
想象一个场景：地图上有好几个着火的点，火势每秒向四周空地蔓延一格，问你整张图被烧完需要多久。如果你对每个着火点分别做一次BFS，然后对每个格子取最小值，复杂度是 O(火源数 * 网格点数)，火源一多就完蛋。
正确做法是超级源点思路：把所有着火点初始化时全部丢进队列，让它们同时开始扩散。第一次出队的轮次，就是该格子距离最近火源的最短时间。整张图只需要一遍BFS，复杂度O(V+E)。
这个思路还可以反着用。假如问题是“所有居民点到最近超市的最大距离”，只要把超市的位置全部入队，跑一遍多源BFS，每个格子存的dist就是这个格子到最近超市的距离，然后取最大值，一步搞定。
3. 可直接抄作业的三种模板
讲理论不带代码都是耍流氓。这里我把实战里用得最多的三类模板整理了出来，按复杂度从低到高排列。都是C++17可以跑通的标准写法。
3.1 标准BFS漫水+最短路（无权图）
这套模板适合网格图求最短步数，也适合连通块染色。核心结构是dist数组既当访问标记用，又存最短距离。
#include <bits/stdc++.h> using namespace std; int n, m; int grid[505][505]; int dist[505][505]; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; void bfs(int sx, int sy) { memset(dist, -1, sizeof(dist)); queue<pair<int, int>> q; q.push({sx, sy}); dist[sx][sy] = 0; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (dist[nx][ny] != -1) continue; // 已访问过 if (grid[nx][ny] == 1) continue; // 墙 dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } }注意这里我用dist = -1表示未访问，dist非负值既表示已访问又存距离。写习惯了比再开一个visited布尔数组省事。数组大小我按505开的，实际使用时根据数据规模调整，别照抄开小了。
3.2 01-BFS处理变代价漫水
如果你发现地图上的步长代价只有0和1，那强烈建议别用Dijkstra，用双端队列。怕大家原理记不牢，我再画个重点：代价0放队首，代价1放队尾，每次从队首取元素，就能保证距离单调不减。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; int n, m; int grid[MAXN][MAXN]; int dist[MAXN][MAXN]; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; void bfs01(int sx, int sy) { memset(dist, 0x3f, sizeof(dist)); deque<pair<int, int>> dq; dq.push_front({sx, sy}); dist[sx][sy] = 0; while (!dq.empty()) { auto [x, y] = dq.front(); dq.pop_front(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; int w = (grid[nx][ny] == 1); // 墙代价为1，空地代价为0 if (dist[nx][ny] > dist[x][y] + w) { dist[nx][ny] = dist[x][y] + w; if (w == 0) dq.push_front({nx, ny}); else dq.push_back({nx, ny}); } } } }这里有个容易翻车的细节：用memset(dist, 0x3f, sizeof(dist))是让dist初始化为一个很大的数，0x3f3f3f3f大概是十亿级别，比int能容忍的最大值小一点，往上加不会溢出成负数。我见过有人直接用INT_MAX，结果dist[x][y] + w时溢出变成负数，代码跑起来全是错的。
3.3 带状态的分层漫水（状态压缩BFS）
遇到“钥匙开门”这类题，单纯二维坐标已经不够了。你还需要记录当前已经收集了哪些钥匙，这组信息就是“状态”。典型手法是把钥匙集合压成一个二进制掩码，比如1表示有第1把钥匙，2表示第2把，4表示第3把，以此类推，用按位或来累加。
#include <bits/stdc++.h> using namespace std; struct State { int x, y, keyMask; }; int n, m; char grid[505][505]; int dist[505][505][1 << 6]; // 最多6把钥匙 int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; int bfs(int sx, int sy) { memset(dist, -1, sizeof(dist)); queue<State> q; q.push({sx, sy, 0}); dist[sx][sy][0] = 0; while (!q.empty()) { auto [x, y, keyMask] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; char c = grid[nx][ny]; if (c == '#') continue; if (isupper(c)) { // 开门：必须拥有对应钥匙 int need = 1 << (c - 'A'); if ((keyMask & need) == 0) continue; } int newMask = keyMask; if (islower(c)) { newMask |= (1 << (c - 'a')); } if (dist[nx][ny][newMask] != -1) continue; dist[nx][ny][newMask] = dist[x][y][keyMask] + 1; q.push({nx, ny, newMask}); } } // 终点可能是(grid[tx][ty])的某个状态，遍历mask取最小即可 }重点：这类题最容易错的地方，是访问标记只用了二维
dist[x][y]，忽略了同一个物理格子可以在不同钥匙状态下被重复访问。比如先没钥匙路过得去，拿了钥匙再回来也完全可能。所以dist第三维必须加上钥匙掩码，否则会漏掉大量可行路径。
4. 真实场景拆解：三个拿来就能复盘的例子
4.1 基础连通块漫水：染色覆盖率
这类题在图像处理里非常常见，描述通常是：给一个二值图，从某个点开始填充，把所有相邻的同色区域改色。算法题里则化身成“岛屿数量”“被包围的区域”之类。
处理这类问题的关键不是BFS过程本身，而是如何判定“该不该染”。我习惯把所有判定条件集中在入队前一次性检查。比如剑指Offer风格的“矩阵中的路径”类题，你在入队时就要保证：不越界、没访问过、颜色匹配。这样写出来的代码清晰，调试的时候只要盯一个地方。
我实操中积累的一个小经验：如果你要统计连通块个数，不是从一个点开始漫水，而是要遍历全图，每遇到一个没访问过且符合条件的目标点，就作为种子启动一次BFS，计数器加一。遍历过程和BFS染色的访问标记要共用同一个数组，防止重复启动。
4.2 多源BFS城市消防站选址问题
模拟一个场景：一个城市网格里，有些格子是消防站，有些是居民楼，问你“离它最近的消防站最远的居民楼”有多远。这就是典型多源BFS。
我第一次做这题时走了弯路，对每个消防站单独BFS一次，然后对每个居民楼取所有次结果的最小值。第一次跑觉得没毛病，但数据规模一大就超时，因为复杂度接近O(F * N * M)。
后来想通了，直接建一个虚拟超级源点，把所有消防站的距离设为0一并入队，跑一遍BFS。BFS队列的先进先出特性保证每个格子第一次被访问时，就是从最近消防站扩散过来的距离。十几行代码，把时间复杂度压到单纯O(N*M)。这类问题的经典应用还包括“求所有海洋格子到最近陆地的最大距离”，思路一模一样。
4.3 带有状态约束的迷宫开门
“收集钥匙再开门”是让人又爱又恨的题。爱是因为思路清晰：BFS状态就是坐标+钥匙集合。恨是因为一旦钥匙数量超过8个，位压缩的状态数就会爆炸，二维数组存不下，得换哈希或者set。
这类题的典型细节是：起点处的钥匙不能漏掉。我踩过一次坑，起点所在的格子本身可能有钥匙，但入队时我只存了mask=0，导致起点钥匙永远拾取不到。正确做法是初始化时先扫一下起点格子，把钥匙并入mask再入队。
另一个细节是门的位置也算可走格。有些朋友一看到大写字母就觉得是墙直接跳过，其实如果手里有对应钥匙，这个门是可以走的。判断逻辑是：先看是不是墙，再看是不是门，门要先查钥匙再决定放不放行。
5. 常见问题与排查技巧实录
5.1 入队时标记还是出队时标记
这是新手翻车率最高的一题，没有之一。
BFS的访问标记必须在入队时做，不能等出队时再做。如果等出队时再标记，同一个节点会被多个邻居重复入队，队列里积压大量重复元素，极端情况下复杂度会从O(V+E)退化到指数级。
我见过最离谱的一次调试经历，就是用出队标记写了迷宫题，小数据能过，大数据直接卡死，排查半天发现是队列里同一坐标重复了几万次。记住一句话：入队即标记，出队只扩展。
5.2 方向数组与边界的顺序问题
方向数组dx/dy写错是低级错误里最常见的。四个方向建议固定顺序：-1,1是上下，0,0是右边，0,0是左边。但因为0重复，写的时候特别容易手滑。我自己的习惯是写出明确注释：
int dx[] = {-1, 1, 0, 0}; // 上 下 左 右 int dy[] = {0, 0, -1, 1};如果题目要求八方向（斜着也能走），就加上对角线：
int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};记不住八方向就别硬记，用一个双重循环枚举偏移量，然后跳过(0,0)即可，但注意它不会调整遍历顺序，某些题目如果对扩展顺序有要求，得单独处理。
5.3 状态数组维度开错
带状态BFS最容易出的问题就是第三维开小了。题目说有5把钥匙，掩码范围是0到31，开dist[505][505][32]正好。如果你开成了[505][505][5]，恭喜你，狠狠踩了数组越界的坑。
C++的数组越界往往是静默崩溃，程序不报错，但结果全是错的。排查时我一般先看dist的第三维下标最大值，手算一下1 << k的结果，然后对照数组声明。
如果钥匙数量超过10甚至到20，位压缩状态太多，内存可能装不下。这时候就得考虑改用unordered_set哈希状态，或者用双向BFS剪枝。说这些可能有点超纲，但提前知道了总归是好事。
5.4 递归DFS爆栈问题
我再次强调一遍，凡是能用BFS解决的问题，尽量别用DFS。即使DFS代码短，在数据规模稍大一点时就可能爆栈。有些面试官确实指定要看到DFS解法，那至少得把递归深度控制在几千以内，不要在一个超大连通块里裸奔。
如果你想在DFS场景下避免爆栈，可以改递归为显式栈。原理和BFS的队列非常像，只是把队列换成了栈，访问顺序从层序变成了深度优先。代码写起来比BFS还要拗口些，但至少不会爆栈。
5.5 判断是不是真的需要最短路
有些题目表面看起来像是求最短路径，但其实只需要判断连通性。比如问“从A能不能走到B”，直接BFS染色，碰到B就返回true，全程跟距离没有任何关系，不需要dist数组。
还有一种题型，问的是“最少开几扇门才能到达终点”，但门开关不影响移动代价，这时本质上可能是01-BFS而不是普通BFS。要仔细读题，确认每一步的代价是否完全一致。如果一致，就是标准BFS；如果有的步代价为0，有的为1，就得用01-BFS；如果代价更多变，才轮到Dijkstra。
6. 为什么这组组合技比单学的威力大得多
聊点实在的。刷题这件事，掌握单个算法只是第一步，真正拉开差距的是能不能看出题目背后的组合结构。Flood Fill和最短路模型的组合，本质上提供了一种思考框架：把图中“可达性”和“最优性”揉在一起，从扩散的视角去理解路径规划。
我在指导别人的时候经常打一个比方：普通DFS/BFS像是在屋里拿着手电筒乱照，照到哪个角落算哪个；而带着最短路思想的漫水法像是一盆水泼出去，水会自己找到所有能渗进去的缝隙，而且渗透的时间天然告诉你哪条路最近。学会了这个视角，你会突然发现很多题目都可以用“让水漫出去”的方式来做。
多源BFS和01-BFS这两类题，很多人到面试前都搞不清楚，其实就是没想通漫水思想。想通了就一句话：无非是把多个起点倒进同一盆水里，或者往水里加了不同流速的地形。
更多扩展方向：
- 分层图最短路：如果状态不只是坐标，还加上“用了某种道具”，就可以理解为在多个“图层”之间漫水。
- 双向BFS：两个水盆同时朝对方泼水，在中点交汇，搜索空间大幅缩小。
- A*搜索：给漫水过程加一个“倾向于终点方向扩散”的启发式引导，就是A*了。
这些高级玩法，都是从Flood Fill与最短路模型这两个地基上长出来的。地基打得稳，往上盖什么都踏实。
7. 最后再分享一点个人偏见
算法这行有个奇妙的地方：同样一盘菜，每个人的吃法不一样。有人非要背下所有模板细节才敢动手，有人上来就干然后被各种坑狠狠教育。我自己属于后者，所以我特别建议你，看到这篇里的代码，别急着往下滑，先自己开个IDE把基础版BFS敲一遍，然后故意把“入队标记”改成“出队标记”，看看会出现什么诡异的结果。
踩坑从来不是坏事，前提是你知道自己为什么踩。Flood Fill和它延伸出的最短路模型，我大概刷了不下两百道题才觉得稍微通透了些。这个过程中最值钱的收获，不是背住了多少模板，而是形成了“这题本质上是个漫水问题”的条件反射。希望这篇文章能帮你提前建立这个反射通道。
工具选型上，如果本地刷题，VS Code配C++插件完全够用；如果只想快速验证，在线编辑器也挺好，关键是趁早动手。真正学到脑子里去的，永远是那些你自己亲手敲出来、亲手调过的代码。
