1101.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

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

int n,m,visited[80][80],tx,ty;
char g[80][80];
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

struct cord{
	int x,y;
	int step;
}node[10000];

int check(int x,int y)
{
	if (x<0||y<0) return 0;
	if (x>m||y>n) return 0;
	if (g[x][y]=='X'&&!(x==tx&&y==ty)) return 0;
	return 1;
}

int bfs(int sx,int sy)
{
	int i,j,front=0,rear=0,t1,t2,x,y;
	node[0].x=sx;node[0].y=sy;node[0].step=0;
	visited[sx][sy]=1;
	while(rear<=front){
		x=node[rear].x;
		y=node[rear].y;
		for(i=0;i<4;i++){
			for(j=1;check((t1=x+j*d[i][0]),(t2=y+j*d[i][1]));j++){
				if (visited[t1][t2]) continue;
				if (t1==tx&&t2==ty) return node[rear].step+1;
				front++;
				node[front].x=t1;
				node[front].y=t2;
				node[front].step=node[rear].step+1;
				visited[t1][t2]=1;
			}
		}
		rear++;
	}
	return -1;
}

int main()
{
	int i,j,t,sx,sy,count=0,count2;
//	freopen("in.txt","r",stdin);
	while(1){
		scanf("%d%d",&m,&n);
		if (n==0) return 0;
		printf("Board #%d:\n",++count);
		for(i=1;i<=n;i++){
			getchar();
			for(j=1;j<=m;j++) g[j][i]=getchar();
		}
		for(i=0;i<=m+1;i++) g[i][0]=g[i][n+1]=' ';
		for(i=0;i<=n+1;i++) g[0][i]=g[m+1][i]=' ';
		n++,m++;
		count2=0;
		while(1){
			scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
			if (sx==0) break;
			printf("Pair %d: ",++count2);
			memset(visited,0,sizeof(visited));
			t=bfs(sx,sy);
			if (t<=0){
				printf("impossible.\n");
			}else printf("%d segments.\n",t);
		}
		printf("\n");
	}
}