GESP6级C++考试语法知识（泛洪算法 2、多源泛洪与连通块）

第二课 多源 Flood Fill一、什么叫多源1、先来看一个故事。《森林里的大火》森林地图 有两个地方着火了。2、问题一分钟以后哪些地方会着火再过一分钟最终整个森林多久烧完3、是不是发现火不是一个地方开始烧。而是很多地方一起烧。这就是多源搜索Multiple Source Search二、为什么DFS不适合1、假设A点着火B点也着火2、如果DFSA ↓↓↓↓↓↓↓↓ 一直烧到底 然后回来 再烧B现实吗当然不是。3、现实应该第一分钟 A扩散 B扩散 第二分钟 A继续扩散 B继续扩散 第三分钟 继续……所以多个源点同时扩散一般都使用BFS4、这是一个比赛经验多源 最短时间 BFS三、多源BFS模板1、例如1地图0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0其中1表示火源。2第一步把所有火源加入队列。queuepairint,int q; for(int i0;in;i) { for(int j0;jm;j) { if(mp[i][j]1) { q.push({i,j}); } } }注意不是放一个。而是全部放进去3然后开始普通BFSwhile(!q.empty()) { auto curq.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 ans0; for(int i0;in;i) { for(int j0;jm;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;即可。②最小面积维护ansmin(ans,cnt);③周长DFS过程中统计边界。④染色例如111100 111100 001111变成222200 222200 003333不同连通块不同编号。有的地图题这样做。十、DFS版Flood Fill与BFS版Flood Fill比较下面这张表是竞赛中必须掌握的。对比DFSBFS数据结构递归/栈队列搜索方式一条路走到底一层一层扩散像什么探险家水波纹是否适合最短路❌✅是否适合统计连通块✅✅是否适合多源扩散❌✅编码难度简单稍复杂一句口诀数块用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 area1; for(int k0;k4;k) { int nxxdx[k]; int nyydy[k]; if(nx0nxnny0nymmp[nx][ny]1) { areadfs(nx,ny); } } return area; }扫描地图for(int i0;in;i) { for(int j0;jm;j) { if(mp[i][j]1) { block; int areadfs(i,j); bestmax(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——负责按层扩散解决最短时间、最短距离和多源传播问题。