farm irrigation(dfs).cpp

杭电acm解题报告2001---2099.

//也可用并查集
#include <cstdio>
#include <string>

const int NMAX = 60;
 int n,m;
 struct node {
	bool up,down,left,right;
 }pipe[11];
 node map[NMAX][NMAX];
 char line[NMAX];
 bool vis[NMAX][NMAX];

void init_pipe()
{
	memset(pipe,false,sizeof(pipe));
	pipe[0].left = pipe[0].up = true;
	pipe[1].right = pipe[1].up = true;
	pipe[2].left = pipe[2].down = true;
	pipe[3].right = pipe[3].down = true;
	pipe[4].up = pipe[4].down = true;
	pipe[5].left = pipe[5].right = true;
	pipe[6].left = pipe[6].right = pipe[6].up = true;
	pipe[7].left = pipe[7].up = pipe[7].down = true;
	pipe[8].left = pipe[8].right = pipe[8].down = true;
	pipe[9].right = pipe[9].up = pipe[9].down = true;
	pipe[10].left = pipe[10].right = pipe[10].up = pipe[10].down = true;
}

void dfs(int x,int y,int d)
{	
	if(x<0 || y<0 || x>=n || y>=m || vis[x][y]) {
		return ;
	}
	switch(d) {
	case 1://up to
		if(!map[x][y].down) {
			return ;
		}
		break;
	case 2://down to
		if(!map[x][y].up) {
			return ;
		}
		break;
	case 3://left to
		if(!map[x][y].right) {
			return ;
		}
		break;
	case 4://right to
		if(!map[x][y].left) {
			return ;
		}
		break;
	}
	vis[x][y] = true;
	if(map[x][y].up) {
		dfs(x-1, y, 1);
	}
	if(map[x][y].down) {
		dfs(x+1, y, 2);
	}
	if(map[x][y].left) {
		dfs(x, y-1, 3);
	}
	if(map[x][y].right) {
		dfs(x, y+1, 4);
	}
}

int main()
{
	int i,j;

	init_pipe();
	while(scanf("%d %d", &n,&m)==2) {
		if(n==-1 && m==-1) {
			break;
		}
		getchar();
		for(i=0;i<n;i++) {
			gets(line);
			for(j=0;j<m;j++) {
				map[i][j] = pipe[ line[j]-'A' ];
			}
		}
		memset(vis,0,sizeof(vis));
		int spring = 0;
		for(i=0;i<n;i++) {
			for(j=0;j<m;j++) {
				if(!vis[i][j]) {
					dfs(i,j,0);
					spring ++;
				}
			}
		}
		printf("%d\n", spring);
	}
}