首页 > 代码库 > 灌水导论——灌水法初步
灌水导论——灌水法初步
灌水法：
Flood Fill 直译为大水漫灌，会造成土地盐碱化。。。。。。
但是，在OI中，灌水不失为水搜索的一种好方法呢~~
灌水的思想：
灌水的思想其实就是从一个点（水源）出发，将符合条件可以到达（水可以灌到的地方）的点打标记，或者说染色。然后我们就可以通过染色的情况来处理一些问题。
空说理论没什么意义，结合一个例（shui）题说一下吧：
POJ2386 Lake Counting
题目简述：
给你一张n*m二维图，由"W"和"."组成，"."表示陆地，"W"表示水。水不流动（难度低到爆表的表现），要求求出水坑的个数（八连块）。
题解：
灌水啊~~
我们用vis[][]来记录是否找过（就是染色），每找到一个W且没有染过色的我们就从这个点灌水染色，且每次找到这样一个点就cnt++；最后输出cnt就是统计出来的数目了。
下面是很水很水的代码：
1 #include<iostream> 2 using namespace std; 3 int n,m; 4 char a[105][105]; 5 int cnt=0; 6 bool vis[105][105]; 7 void flood(int x,int y) 8 { 9 if(x>n || x<1 || y<1 || y>m)return;10 vis[x][y]=true;11 if(!vis[x][y+1] && a[x][y+1]==‘W‘)flood(x,y+1);12 if(!vis[x][y-1] && a[x][y-1]==‘W‘)flood(x,y-1);13 if(!vis[x+1][y] && a[x+1][y]==‘W‘)flood(x+1,y);14 if(!vis[x-1][y] && a[x-1][y]==‘W‘)flood(x-1,y);15 if(!vis[x+1][y+1] && a[x+1][y+1]==‘W‘)flood(x+1,y+1);16 if(!vis[x-1][y-1] && a[x-1][y-1]==‘W‘)flood(x-1,y-1);17 if(!vis[x+1][y-1] && a[x+1][y-1]==‘W‘)flood(x+1,y-1);18 if(!vis[x-1][y+1] && a[x-1][y+1]==‘W‘)flood(x-1,y+1);19 }20 int main()21 {22 cin>>n>>m;23 for(int i=1;i<=n;i++)24 {25 for(int j=1;j<=m;j++)26 {27 cin>>a[i][j];28 }29 }30 for(int i=1;i<=n;i++)31 {32 for(int j=1;j<=m;j++)33 {34 if(!vis[i][j] && a[i][j]==‘W‘)35 {36 cnt++;37 flood(i,j);38 }39 }40 }41 cout<<cnt;42 return 0;43 }
本人弱弱，求指教。
灌水导论——灌水法初步
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。