关于dfs积水类的问题

题(Lake Counting (poj no.2386))
题目是这样的,有一个大小为NxM的园子,雨后积水了,问你有几个水洼。
Sample Input
10 12

W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

Sample Output

3

思路是这样的:用一次dfs就会将有积水的地方和他所相连的部分都变成无积水 总共dfs的次数就是水洼的个数
代码如下:

#include<stdio.h>
char a[1000][1200];
void dfs(int x,int y)
{
   
	a[x][y]='.';
	for(int dx=-1;dx<=1;dx++)
		for(int dy=-1;dy<=1;dy++)
			{
   
				int nx=x+dx,ny=y+dy;
				if(nx>=0&&nx<n&&ny>=0&&ny<m&&a[nx][ny]=='W')
					dfs(nx,ny);
			}
		return;
}
int main()
{
   
		int cnt;
		int i=0;int j=0;
		int n,m;
			while(scanf("%d%d",&n,&m)!=EOF){
   
			cnt=0;
			for(i=0;i<=n-1;i++)
			scanf("%s",a[i]);
			for(i=0;i<=n-1;i++)
				for(j=0;j<=m-1;j++)
				if(a[i][j]=='W')
				{
   
				dfs(i,j);
				cnt++;
				}
			printf("%d\n",cnt);
	}
}
全部评论

相关推荐

贪食滴🐶:你说熟悉扣篮的底层原理,有过隔扣职业球员的实战经验吗
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务