farm irrigation.cpp

是POJ上的一道搜索题,用VC调试通过,提交通过

#include<stdio.h>
#include<string.h>

int m,n;
char map[55][55];
bool visited[55][55],way[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};
int res;

void dfs(int x,int y)
{
	int k;
	k=map[x][y]-'A';
	if(y+1<n&&!visited[x][y+1]&&way[k][1]&&way[map[x][y+1]-'A'][3])
	{
		visited[x][y+1]=1;
		dfs(x,y+1);
	}
	if(x+1<m&&!visited[x+1][y]&&way[k][2]&&way[map[x+1][y]-'A'][0])
	{
		visited[x+1][y]=1;
		dfs(x+1,y);
	}
	if(y-1>=0&&!visited[x][y-1]&&way[k][3]&&way[map[x][y-1]-'A'][1])
	{
		visited[x][y-1]=1;
		dfs(x,y-1);
	}
	if(x-1>=0&&!visited[x-1][y]&&way[k][0]&&way[map[x-1][y]-'A'][2])
	{
		visited[x-1][y]=1;
		dfs(x-1,y);
	}
}
	

int main()
{
	int i,j;
	freopen("in.txt","r",stdin);
	scanf("%d%d",&m,&n);
	while(m!=-1)
	{
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
				scanf(" %c",&map[i][j]);
		memset(visited,0,sizeof(visited));
		res=0;
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
				if(!visited[i][j])
				{
					res++;
					visited[i][j]=1;
					dfs(i,j);
				}
		printf("%d\n",res);
		scanf("%d%d",&m,&n);
	}
	return 0;
}