第二课 多源 Flood Fill
一、什么叫"多源"？
1、先来看一个故事。
《森林里的大火》
森林地图：
🌲🌲🌲🌲🌲 🌲🔥🌲🌲🌲 🌲🌲🌲🔥🌲 🌲🌲🌲🌲🌲 🌲🌲🌲🌲🌲有两个地方着火了。
2、问题：
一分钟以后，哪些地方会着火？
再过一分钟？
最终整个森林多久烧完？
3、是不是发现：
火不是一个地方开始烧。
而是：
很多地方一起烧。
这就是：
多源搜索（Multiple Source Search）
二、为什么DFS不适合？
1、假设：
A点着火
B点也着火
2、如果DFS：
A ↓↓↓↓↓↓↓↓ 一直烧到底 然后回来 再烧B现实吗？
当然不是。
3、现实应该：
第一分钟 A扩散 B扩散 第二分钟 A继续扩散 B继续扩散 第三分钟 继续……所以：
多个源点同时扩散，一般都使用BFS！
4、这是一个比赛经验：
多源 + 最短时间 = BFS
三、多源BFS模板
1、例如：
（1）地图：
0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0其中：
1表示火源。
（2）第一步：
把所有火源加入队列。
queue<pair<int,int>> q; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(mp[i][j]==1) { q.push({i,j}); } } }注意：
不是放一个。
而是：
全部放进去！
（3）然后开始普通BFS：
while(!q.empty()) { auto cur=q.front(); q.pop(); ... }这就是：
多源BFS
四、经典例题1——腐烂的橘子
1、这是学习多源BFS最经典的一题。
（1）地图：
2 1 1 1 1 0 0 1 1其中：
0 空地 1 好橘子 2 坏橘子（2）规则：
一分钟以后：
坏橘子感染上下左右。
问：
全部感染需要多久？
第一分钟：
2 2 1 2 1 0 0 1 1第二分钟：
2 2 2 2 2 0 0 1 1第三分钟：
2 2 2 2 2 0 0 2 2完成。
答案：
3分钟。
2、为什么必须BFS？
因为：
所有坏橘子：
一起传播。
DFS无法表示：
"同时传播"。
五、经典例题2——离最近医院有多远
1、地图：
0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0其中：
1是医院。
问题：
每个格子离最近医院距离是多少？
如果每个点DFS一次：
复杂度：
O(n²×n²)太慢。
怎么办？
2、所有医院：
一起BFS！
第一次到达某点：
就是最近距离。
这是多源BFS最重要的性质。
六、 连通块（Connected Component）
终于来到Flood Fill最重要的应用。
1、什么叫连通块？
（1）例如：
1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 0 0请问：
有几块陆地？
（2）画一下：
第一块：
■■ ■■第二块：
■■ ■第三块：
■答案：
3块。
（3）这三块：
就叫：
三个连通块。
2、连通块定义
（1）一句话：
能互相到达的一整片区域。
（2）例如：
□□□□□ □■■■□ □■■■□ □□□□□整个黑色：
就是一个连通块。
七、统计连通块的方法
1、扫描整个地图：
①②③④⑤ ⑥⑦⑧⑨⑩遇见：
1说明：
发现新的岛屿。
2、于是：
DFS。
把整个岛：
全部染成2。
3、例如：
开始：
1100 1100 0011第一次：
2200 2200 0011岛屿数量：
+1
继续扫描。
4、最后：
2200 2200 0022数量：
2。
5、代码：
int ans=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(mp[i][j]==1) { ans++; dfs(i,j); } } }这是：
统计连通块的万能模板。
八、经典例题——岛屿数量
1、输入：
11110 11010 11000 000002、答案：
1。
因为：
全部连着。
3、输入：
11000 11000 00100 00011答案：
3。
这是：
Flood Fill第一经典题。
九、连通块还能求什么？
不仅数量。
还能求：
①最大面积
例如：
11100 10000 00111第一块：
面积：
4
第二块：
面积：
3
答案：
4。
DFS里面：
增加：
cnt++;即可。
②最小面积
维护：
ans=min(ans,cnt);③周长
DFS过程中：
统计边界。
④染色
例如：
111100 111100 001111变成：
222200 222200 003333不同连通块：
不同编号。
有的地图题：
这样做。
十、DFS版Flood Fill与BFS版Flood Fill比较
下面这张表，是竞赛中必须掌握的。
| 对比 | DFS | BFS |
|---|---|---|
| 数据结构 | 递归/栈 | 队列 |
| 搜索方式 | 一条路走到底 | 一层一层扩散 |
| 像什么 | 探险家 | 水波纹 |
| 是否适合最短路 | ❌ | ✅ |
| 是否适合统计连通块 | ✅ | ✅ |
| 是否适合多源扩散 | ❌ | ✅ |
| 编码难度 | 简单 | 稍复杂 |
一句口诀：
数块用DFS，扩散用BFS；求路一般BFS，染色两者都可以。
十一、一道综合例题
1、地图：
1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1要求：
有几个连通块？
最大连通块面积是多少？
2、思路：
定义两个变量：
int block = 0; // 连通块数量 int best = 0; // 最大面积3、DFS返回面积：
int dfs(int x,int y) { mp[x][y]=2; int area=1; for(int k=0;k<4;k++) { int nx=x+dx[k]; int ny=y+dy[k]; if(nx>=0&&nx<n&&ny>=0&&ny<m&&mp[nx][ny]==1) { area+=dfs(nx,ny); } } return area; }扫描地图：
for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(mp[i][j]==1) { block++; int area=dfs(i,j); best=max(best,area); } } }最终输出：
连通块数量：6 最大连通块面积：3这个例子体现了 Flood Fill 的威力：一次搜索不仅能完成染色，还能顺便统计面积、周长、边界等各种信息。
十二、竞赛中的"Flood Fill 家族"
当你学完今天的内容后，会发现很多看似不同的题，其实都是同一种思想。
| 题目 | 本质 |
|---|---|
| 岛屿数量 | 连通块统计 |
| 最大岛屿 | 连通块面积 |
| 封闭岛屿 | Flood Fill + 边界判断 |
| 飞地数量 | 从边界开始 Flood Fill |
| 腐烂的橘子 | 多源 BFS |
| 最近医院 | 多源 BFS 最短距离 |
| 地图染色 | Flood Fill |
| 迷宫可达性 | DFS/BFS 搜索 |
| 最短迷宫 | BFS 最短路 |
所以很多同学会觉得自己在学很多算法，其实背后的核心只有两个：
DFS Flood Fill——负责找到、统计和染色整个连通区域。
BFS Flood Fill——负责按层扩散，解决最短时间、最短距离和多源传播问题。
