信息奥赛一本通1249：Lake Counting

【题目描述】
题意：有一块N×M的土地，雨后积起了水，有水标记为‘W’，干燥为‘.’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼？

【输入】
第一行为N,M(1≤N,M≤110)。

下面为N*M的土地示意图。

【输出】
一行，共有的水洼数。

【输入样例】
10 12
W…WW.
.WWW…WWW
…WW…WW.
…WW.
…W…
…W…W…
.W.W…WW.
W.W.W…W.
.W.W…W.
…W…W.
【输出样例】
3

题解：
这和书上P305 例8.2 细胞问题，类似，只不要这里水洼周围八个方向有水洼的，都看成一个水洼。

代码如下：

//1249：Lake Counting
#include<iostream>
#include<cstdio>
using namespace std;
int dx[8]={-1,-1,0,1,1,1,0,-1},
	dy[8]={0,1,1,1,0,-1,-1,-1};//八个方向，上、右上、右、右下、下、左下、左、左上 
int num=0,n,m;
char map[111][111]; 
void doit(int p,int q)
{
	int x,y,t,w,i;
	//1<=n,m<=110,最多12100个点，队列最多有12100个元素,
	//队列从1开始标记，到12101结束 
	int h[12101][2];
	num++;
	map[p][q]='.';
	t=0;
	w=1;
	h[1][1]=p;
	h[1][2]=q;
	do
	{
		t++;
		for(i=0;i<=7;i++)
		{
			x=h[t][1]+dx[i];
			y=h[t][2]+dy[i];
			if((x>=1)&&(x<=n)&&(y>=1)&&(y<=m)&&(map[x][y]=='W'))
			{
				w++;
				h[w][1]=x;
				h[w][2]=y;
				map[x][y]='.s';
			}
		}
	}while(t<w);
}
int main()
{
	int i,j;
	char s[100],ch;
	scanf("%d%d\n",&n,&m);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			cin>>map[i][j];

	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(map[i][j]=='W')//找到水洼 
				doit(i,j);
	printf("%d",num);
    return 0;
}