POJ 2386 Lake Counting DFS水水

http://poj.org/problem?id=2386

题目大意：

有一个大小为N*M的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼？

思路：

水题~直接DFS，DFS过程把途中表示水洼的W改为‘.‘，看DFS了几次即可。

#include<cstdio>
#include<cstring>
const int MAXN=100+10;
char map[MAXN][MAXN];
int n,m;
void dfs(int x,int y)
{
	if(map[x][y]==‘.‘)
		return ;

	 map[x][y]=‘.‘;
	 dfs(x+1,y+1);
	 dfs(x,y+1);
	 dfs(x-1,y+1);
	 dfs(x-1,y);
	 dfs(x-1,y-1);
	 dfs(x,y-1);
	 dfs(x+1,y-1);
	 dfs(x+1,y);	
}

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=1;i<=n;i++)
			scanf("%s",map[i]+1);

		for(int i=0;i<=n+1;i++)
			map[i][0]=map[i][m+1]=‘.‘;
		for(int i=0;i<=m+1;i++)
			map[0][i]=map[n+1][i]=‘.‘;

		int ans=0;
		for(int i=0;i<=n+1;i++)
		{
			for(int j=0;j<=m+1;j++)
			{
				if(map[i][j]==‘W‘) {
					ans++;
					dfs(i,j);
				}
			}
		}
		printf("%d\n",ans);
	}

	return 0;
}

POJ 2386 Lake Counting DFS水水

原文：http://blog.csdn.net/murmured/article/details/19697783