ls学习笔记note25：Flood fill（洪水填充）算法
paperghost_ls · · 个人记录
在caioj里就做过有关于Flood fill的题，现在想拿出来讲讲
这个算法因为思路类似洪水从一个区域扩散到所有能到达的区域而得名，大概是从一个起始节点开始把附近与其连通的节点提取出或填充成不同颜色颜色，直到封闭区域内的所有节点都被处理过或封闭区域内的所有点都被填充新颜色为止，是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典算法，有许多实现方式，基本上都显式的或隐式的使用了队列或者栈
Flood fill算法接受三个参数：起始节点，目标节点特征和针对提取对象要执行的处理
洪水填充算法实现最常见有四邻域填充法，八邻域填充法，基于扫描线填充方法
根据实现又可以分为递归与非递归（基于栈）。
最简单的实现方法是采用dfs的递归方法，也可以采用bfs的迭代来实现。
基于递归实现的Flood Fill算法有个致命的缺点，就是对于大的区域填充时可能导致栈溢出错误
除提出连通区域外，还可以应用于计算从某一节点开始，到可能到达其他所有节点的距离。比如解决像走迷宫这类的问题
更详细一点说：
dfs：取一个结点，对其标记，然后标记它所有的邻结点。对它的每一个邻结点这么一直递归下去完成搜索
bfs：与深搜不同的是，广搜把结点加入队列中。
广度扫描（不常见）：每个结点有两个值，一个用来记录它属于哪个连通子图（c），一个用来标记是否已经访问（v）。算法对每一个未访问而在某个连通子图当中的结点扫描，将其标记访问，然后把它的邻结点的（c）值改为当前结点的（c）值
这同时也是个图论算法，前不久我们学到的强连通分量，通过给图中的点染色，最终使得同一个连通分量的顶点颜色相同，不同连通分量的点颜色不同
好了，让我们看看几个样例：
分析问题可知，这道题实际上就是一个积水的点与上下左右左上右上左下右下这8个格子，只要有一个也是积水的话那么就是在一个池塘，最后问你整个图有多少个池塘
这个其实也蛮简单的，无非就是搜到积水的点就访问这8个格子，然后重复以上操作。
这和Flood fill算法的思路一致，就是找到一个符合条件的点，就不断访问它附近的点，直到搜完为止，所以把这个归到Flood fill算法里面
#include<cstdio>
using namespace std;
int ans;
int n,m;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
char a[110][110];
void dfs(int x,int y)
{
a[x][y]='.';//标记为没有
for(int t=0;t<8;t++)
{
int xx=x+dx[t],yy=y+dy[t];
if(a[xx][yy]=='W')dfs(xx,yy);//如果附近的点也是，一直访问，直到没有附近积水的点
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]=='W')dfs(i,j),ans++;//因为搜完以后，这个池塘就都被搜过，已经清空了，这就是一个池塘
printf("%d\n",ans);
return 0;
}这个和上面这题差不多，只是把池塘（这题是连续建筑）总数改成了池塘的节点个数，只要比较一下就好
#include<cstdio>
#include<algorithm>
using namespace std;
int ans;
int n,m;
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
char a[1100][110];
int dfs(int x,int y)
{
a[x][y]='.';int sum=1;//从自己开始，记录自己能访问到几个符合条件的点
for(int t=0;t<4;t++)
{
int xx=x+dx[t],yy=y+dy[t];
if(a[xx][yy]=='*')sum+=dfs(xx,yy);//加上
}
return sum;/返回
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]=='*')ans=max(ans,dfs(i,j));//比较大小
printf("%d\n",ans);
return 0;
}这一题运用的不是很明显，但是这个运用到了图论，这个有点强连通的味道（好像就是强连通吧），也就还是一直搜下去
#include<cstdio>
using namespace std;
int a[110000],ans[110000],deep[110000];//deep表示在一个联通分量里的节点层数
bool v[110000];//表示该点已被访问过
void dfs(int x,int len)
{
v[x]=1;deep[x]=len;
if(ans[a[x]])ans[x]=ans[a[x]]+1;//如果下一个去的房间已经有了答案，那么我就是那个答案+1
else if(deep[a[x]])//如果下一个去的房间没有答案，但是已经有了层数，说明成了一个环
{
ans[x]=(deep[x]-deep[a[x]]+1);//计算这个环有多大
int i=a[x];//从下一个房间开始
while(i!=x)//因为是个环，在同一联通分量里面
{
ans[i]=ans[x];//赋值
i=a[i];//找下一个连通分量的节点
}
}
else
{
dfs(a[x],len+1);//不然就去下一个房间
if(!ans[x])ans[x]=ans[a[x]]+1;//如果没有出现环，那么就等于下一个房间+1
}
}
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
if(!v[i])dfs(i,0);//没被遍历过的话
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);//输出答案
}总结一下（个人观点，有错或有问题的地方欢迎留言指正好像也没什么人看我博客吧）：
Flood fill应该没有什么固定模板，应该只是一种思想。也不是什么高深的东西，貌似我们也经常使用这种算法的思想
所以，其实算法也没有这么难而是超jb难，至少没有你想象的那么难♂
加油吧少年，路还很长，拒绝颓废是不可能的，朝着伟大的目标前进吧！