图像里的魔法——泛洪算法Flood Fill一、先讲一个生活中的故事小明有一张黑白地图######## #......# #.####.# #.#..#.# #......# ########其中#表示墙.表示空地现在小明拿着一桶颜料点击一个地方 ↓ 把和它连在一起的所有空地染成红色这是不是很像画图软件里的“油漆桶工具”比如你点击一个区域........ ..####.. ..#..#.. ..####.. ........油漆会自动扩散RRRRRRRR RR####RR RR#..#RR RR####RR RRRRRRRR这个过程就是Flood Fill泛洪算法二、泛洪算法解决什么问题一句话从一个点出发把所有“连通”的相同区域找出来。关键词1. 从一个点开始例如(2,3)↓2. 向四周扩散看看上 下 左 右↓3. 如果符合条件继续扩散像水流一样↑ | ← ← 起点 → → | ↓三、二维地图怎么表示计算机里面地图就是二维数组。例如1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 1Cint mp[5][5];表示mp[行][列]例如mp[2][3]就是第2行第3列。四、泛洪算法的核心思想假设0代表土地1代表障碍地图0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0从(0,0)开始。我们想把所有和它连接的0变成2。过程第一步染当前位置2 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0然后检查上 下 左 右第二步向右2 2 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0继续2 2 2 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0直到所有连接区域完成。五、DFS实现泛洪算法最经典1. 定义方向因为只能走上 下 左 右所以int dx[4]{-1,1,0,0}; int dy[4]{0,0,-1,1};解释第0种x-1,y向上第1种x1,y向下第2种x,y-1向左第3种x,y1向右六、写DFS函数模板void dfs(int x,int y) { }表示现在站在(x,y)这个位置。第一步染色为什么因为如果不标记会无限循环。例如A - B B - A A - B ...所以进入一个点马上标记。代码mp[x][y]2;第二步尝试四个方向for(int i0;i4;i) { }第三步计算新坐标int nxxdx[i]; int nyydy[i];比如现在x3 y4向上nx2 ny4第四步判断能不能走需要满足条件1不能越界例如-1行不存在。所以nx0条件2必须是目标颜色比如只能走0mp[nx][ny]0完整if(nx0nxn ny0nym mp[nx][ny]0) { dfs(nx,ny); }七、完整C代码题目把和起点连通的0全部变成2。#includeiostream using namespace std; int n,m; int mp[100][100]; int dx[4]{-1,1,0,0}; int dy[4]{0,0,-1,1}; void dfs(int x,int y) { //1.染色 mp[x][y]2; //2.寻找四个方向 for(int i0;i4;i) { int nxxdx[i]; int nyydy[i]; //3.判断是否可以继续 if(nx0nxn ny0nym mp[nx][ny]0) { dfs(nx,ny); } } } int main() { cinnm; for(int i0;in;i) { for(int j0;jm;j) { cinmp[i][j]; } } int x,y; cinxy; dfs(x,y); for(int i0;in;i) { for(int j0;jm;j) { coutmp[i][j] ; } coutendl; } return 0; }八、学生最容易犯的3个错误错误1忘记标记错误void dfs(int x,int y) { dfs(nx,ny); }没有mp[x][y]2;结果无限递归。为什么例如A B C DA走BA→BB又能走AB→A死循环。错误2方向数组写错很多孩子写int dx[4]{1,1,-1,-1};这是什么变成↘ ↙ ↗ ↖走斜线。如果题目要求上下左右必须int dx[4]{-1,1,0,0}; int dy[4]{0,0,-1,1};错误3边界忘记判断例如第0行再向上-1行数组mp[-1][0]非法。程序可能崩溃输出奇怪结果九、DFS和BFS有什么区别泛洪算法有两种写法DFS深度优先搜索像一个小朋友探险一直走到底 走不通回来特点代码短。适合区域染色连通块BFS广度优先搜索像水波第一圈 第二圈 第三圈使用队列 queue。适合最短距离迷宫最短路十、信奥赛中的经典应用泛洪算法非常重要。以后会遇到1. 统计岛屿数量例如11000 11000 00100 00011有几个岛答案每找到一个1DFS染掉。2. 迷宫连通性判断起点能不能到终点3. 最大区域面积例如0 1 1 1 1 0 1 0 0找最大连通块。4. 填充地图类似画图软件油漆桶十一、给同学们总结一句话泛洪算法就是从一个位置出发像水一样向四周流动把所有能够到达的地方全部处理一遍。记住三个关键第一二维数组表示地图。第二DFS/BFS负责扩散。第三一定要走一步标记一步。对于信奥赛学生来说泛洪算法其实是进入DFS搜索、连通块、图论的第一座桥梁。掌握它以后后面的迷宫问题、岛屿问题、图的遍历、BFS最短路都会顺畅很多。
