1307.txt

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

#include"stdio.h"

bool left[13][13];
bool right[13][13];
bool up[13][13];
bool down[13][13];
int n,m,x1,x2,y1,y2;

bool init()
{
	int i,j,s;
	
	scanf("%d %d %d %d %d %d",&n,&m,&x1,&y1,&x2,&y2);

	if(n==0&&m==0&&x1==0&&x2==0&&y1==0&&y2==0)
		return 0;

	x1--,x2--,y1--,y2--;	
	
	for(i=0;i<n;i++)
	for(j=0;j<m;j++)
	{
		scanf("%d",&s);
		right[i][j] = left[i][j+1]= (s&1);
		down[i][j] = up[i+1][j]= (s&2);
	}

	for(i=0;i<n;i++)
		left[i][0]=true,right[i][m-1]=true;
	for(j=0;j<m;j++)
		up[0][j]=true,down[n-1][j]=true;

	return 1;
}

int sign[13][13];
bool (*pt[])[13]={left,up,right,down};
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};


bool search(int x,int y,int step)
{
	int i;

	sign[x][y]=step;
	
	if(x==x2&&y==y2)return 1;
	
	for(i=0;i<4;i++)
		if( !pt[i][x][y] && sign[x+dx[i]][y+dy[i]]==0 )
		{
			if(search(x+dx[i],y+dy[i],step+1))
				return 1;	
		}
	
	sign[x][y] = -1;
	
	return 0;
}

void doit()
{
	int i,j;
	for(i=0;i<n;i++)
	for(j=0;j<m;j++)
		sign[i][j]=0;
	search(x1,y1,1);
}

void printmap()
{
	int i,j;
	static  int times=1;
	
	printf("Maze %d\n\n",times++);	
       	
	printf("+");
	 
	for(j=0;j<m;j++)
	{
		printf("---+");
	}
	
	for(i=0;i<n;i++)
	{
		printf("\n|");
		for(j=0;j<m;j++)
		{
			if(sign[i][j]>0)printf("%3d",sign[i][j]);
			else if(sign[i][j]==-1)printf("???");
			else printf("   ");
			
			if(right[i][j])printf("|");
			else printf(" ");
		}

		printf("\n+");
		for(j=0;j<m;j++)
		{
		
			if(down[i][j])printf("---");
			else printf("   ");
			printf("+");
		}
	}
	printf("\n\n\n");
}

int main()
{
	while(init())
	{
		doit();
		printmap();
	}
	return 0;
}