poj2386Lake Counting

题意是这样的，给你一个N*M的矩形图，这个图由两个东西组成，‘.‘和‘W‘，
W代表这个地方有水，
.代表这个地方没水。
如果一个有水的地方它的上下左右，左上，坐下，右上，右下也有水，那么
就看成它们连成一块，连在一起的有水的地方看成一个水洼。
现在告诉你N和M以及这个矩形图，要你判断图中有多少个水洼。
我是用dfs做的，
具体做法是首先找一个有水的点，然后如果这个地方有水，则水洼数+1，
然后从这个点出发，进行dfs，把与它相连的有水的地方都变成没水的地方，
也就是‘.‘，这样的话，最后得出的水洼数就是题意所要求的。
代码如下

#include<iostream>
using namespace std;
int row,line;
char map[110][110];
void init()
{
	int i,j;
	scanf("%d%d",&row,&line);
	for(i=0;i<row;i++)
		scanf("%s",map[i]);
}
bool isbeyond(int i,int j)
{
	if(i<0||i>=row||j<0||j>=line)
		return 1;
	return 0;
}
void dfs(int i,int j)
{
	int x,y;
	map[i][j]='.';
	for(x=-1;x<2;x++)
		for(y=-1;y<2;y++)
			if(!isbeyond(i+x,j+y)&&map[i+x][j+y]=='W')
				dfs(i+x,j+y);
}
void solve()
{
	int sum=0,i,j;
	init();
	for(i=0;i<row;i++)
		for(j=0;j<line;j++)
			if(map[i][j]=='W')
			{
				sum++;
				dfs(i,j);
			}
	printf("%d\n",sum);
}
int main()
{
	solve();
}

poj2386Lake Counting,布布扣,bubuko.com

poj2386Lake Counting

原文：http://blog.csdn.net/stl112514/article/details/37499583