学步园

并查集 

 先用一个数组a来保存A-K方块上下左右是否有河道。

然后使用并查集，最后判断有多少个不同的集合。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define N 55
#define M 55
int a[11][4]={  1,0,0,1, 
				1,1,0,0,
				0,0,1,1,
				0,1,1,0,
				1,0,1,0,
				0,1,0,1,
				1,1,0,1,
				1,0,1,1,
				0,1,1,1,
				1,1,1,0,
				1,1,1,1 };
char map[N][M];
int father[N*M];
int num[N*M];

int GetFather(int x)
{
	while(father[x]!=-1)
	{
		x=father[x];
	}
	return x;
}

void Union(int x,int y)
{
	int fx=GetFather(x);
	int fy=GetFather(y);
	if(fx!=fy)
		father[fx]=fy;
}

int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m)&&n+m>=0)
	{
		memset(father,-1,sizeof(father));
		for(int i=0;i<n;i++)
			cin>>map[i];
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				if(i>=1&&a[map[i][j]-'A'][0]&&a[map[i-1][j]-'A'][2])//shang
					Union(m*i+j,m*(i-1)+j);
						
				if(i<n-1&&a[map[i][j]-'A'][2]&&a[map[i+1][j]-'A'][0])//xia
					Union(m*i+j,m*(i+1)+j);
							
				if(j>=1&&a[map[i][j]-'A'][3]&&a[map[i][j-1]-'A'][1])//zuo
					Union(m*i+j,m*i+j-1);
										
				if(j<m-1&&a[map[i][j]-'A'][1]&&a[map[i][j+1]-'A'][3])//you
					Union(m*i+j,m*i+j+1);	
			}
			memset(num,0,sizeof(num));
			for(int i=0;i<n*m;i++)
			{
				if(father[i]==-1)
					num[i]=1;
			}
			int ans=0;
			for(int i=0;i<n*m;i++)
				if(num[i])
					ans++;
			printf("%d\n",ans);
	}
	return 0;
}