2384161_ac_15ms_5936k.cpp

北大大牛代码 1240道题的原代码 超级权威

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

int r, c;
char map[21][21];
int mark[21][21][4];
int pi, pj, bi, bj, ti, tj;
int f, p;
int Bi, Bj;
struct node
{
	int pi, pj;
	int bi, bj;
	char way[10000];
}queue[10000];

int ava(int a, int b)
{
	if(a<0||a>=r||b<0||b>=c)
		return 0;
	if(map[a][b]=='#')
		return 0;
	return 1;
}

int bfs(char way[],int a, int b)
{
	int Pi, Pj, ok;
	int F, R, flag[21][21];
	char tmp[1000], ans[1000];
	int Queue[1000][2], pre[1000];

	
	F = R = -1;
	strcpy(tmp,"");
	tmp[0] = 'Y';
	memset(flag,0,sizeof(flag));
	Pi = queue[p].pi;Pj = queue[p].pj;
	if(a==Pi&&b==Pj)
	{
		way[0] = '\0';
		return 1;
	}
	Queue[++F][0] = Pi,Queue[F][1] = Pj;
	pre[0] = -1;flag[Pi][Pj] = 1;
	ok = 0;
	while(F!=R)
	{
		++R;
		Pi = Queue[R][0];Pj = Queue[R][1];
		if(ava(Pi-1,Pj)&&(Pi-1!=Bi||Pj!=Bj)&&flag[Pi-1][Pj]==0)//up
		{
			flag[Pi-1][Pj] = 1;
			Queue[++F][0] = Pi-1;Queue[F][1] = Pj;
			pre[F] = R;tmp[F] = 'n';
			if(Pi-1==a&&Pj==b)
			{
				ok = 1;
				break;
			}
		}
		if(ava(Pi+1,Pj)&&(Pi+1!=Bi||Pj!=Bj)&&flag[Pi+1][Pj]==0)//down
		{
			flag[Pi+1][Pj] = 1;
			Queue[++F][0] = Pi+1;Queue[F][1] = Pj;
			pre[F] = R;tmp[F] = 's';
			if(Pi+1==a&&Pj==b)
			{
				ok = 1;
				break;
			}
		}
		if(ava(Pi,Pj-1)&&(Pi!=Bi||Pj-1!=Bj)&&flag[Pi][Pj-1]==0)//left
		{
			flag[Pi][Pj-1] = 1;
			Queue[++F][0] = Pi;Queue[F][1] = Pj-1;
			pre[F] = R;tmp[F] = 'w';
			if(Pi==a&&Pj-1==b)
			{
				ok = 1;
				break;
			}
		}
		if(ava(Pi,Pj+1)&&(Pi!=Bi||Pj+1!=Bj)&&flag[Pi][Pj+1]==0)//right
		{
			flag[Pi][Pj+1] = 1;
			Queue[++F][0] = Pi;Queue[F][1] = Pj+1;
			pre[F] = R;tmp[F] = 'e';
			if(Pi==a&&Pj+1==b)
			{
				ok = 1;
				break;
			}
		}
	}
	if(ok)
	{
		for(int i = 0; F != -1; i++)
			ans[i] = tmp[F],F = pre[F];
		ans[i-1] = '\0';
		for(int j = 0; j < i-1; j++)
			way[j] = ans[i-2-j];
		way[j] = '\0';
		return 1;
	}
	else
		return 0;
}

void solve()
{
	char tmp[1000], Tmp[1000];

	f = p = -1;
	queue[++f].bi = bi;queue[f].bj = bj;
	queue[f].pi = pi;queue[f].pj = pj;
	queue[f].way[0] = '\0';
	while(f!=p)
	{
		++p;
		Bi = queue[p].bi,Bj = queue[p].bj;
		if(ava(Bi-1,Bj)&&ava(Bi+1,Bj)&&mark[Bi][Bj][0]==0&&bfs(tmp,Bi+1,Bj))//up
		{
			mark[Bi][Bj][0] = 1;
			queue[++f].bi = Bi-1;queue[f].bj = Bj;
			queue[f].pi = Bi;queue[f].pj = Bj;
			strcat(tmp,"N");
			strcpy(Tmp,queue[p].way);
			strcat(Tmp,tmp);
			strcpy(queue[f].way,Tmp);
			if(Bi-1==ti&&Bj==tj)
			{
				puts(queue[f].way);
				return ;
			}
		}
		if(ava(Bi+1,Bj)&&ava(Bi-1,Bj)&&mark[Bi][Bj][1]==0&&bfs(tmp,Bi-1,Bj))//down
		{
			mark[Bi][Bj][1] = 1;
			queue[++f].bi = Bi+1;queue[f].bj = Bj;
			queue[f].pi = Bi;queue[f].pj = Bj;
			strcat(tmp,"S");
			strcpy(Tmp,queue[p].way);
			strcat(Tmp,tmp);
			strcpy(queue[f].way,Tmp);
			if(Bi+1==ti&&Bj==tj)
			{
				puts(queue[f].way);
				return ;
			}
		}
		if(ava(Bi,Bj-1)&&ava(Bi,Bj+1)&&mark[Bi][Bj][2]==0&&bfs(tmp,Bi,Bj+1))//left
		{
			mark[Bi][Bj][2] = 1;
			queue[++f].bi = Bi;queue[f].bj = Bj-1;
			queue[f].pi = Bi;queue[f].pj = Bj;
			strcat(tmp,"W");
			strcpy(Tmp,queue[p].way);
			strcat(Tmp,tmp);
			strcpy(queue[f].way,Tmp);
			if(Bi==ti&&Bj-1==tj)
			{
				puts(queue[f].way);
				return ;
			}
		}
		if(ava(Bi,Bj+1)&&ava(Bi,Bj-1)&&mark[Bi][Bj][3]==0&&bfs(tmp,Bi,Bj-1))//right
		{
			mark[Bi][Bj][3] = 1;
			queue[++f].bi = Bi;queue[f].bj = Bj+1;
			queue[f].pi = Bi;queue[f].pj = Bj;
			strcat(tmp,"E");
			strcpy(Tmp,queue[p].way);
			strcat(Tmp,tmp);
			strcpy(queue[f].way,Tmp);
			if(Bi==ti&&Bj+1==tj)
			{
				puts(queue[f].way);
				return ;
			}
		}
	}
	printf("Impossible.\n");
}

void input()
{
	int i, j;

	for(i = 0; i < r; i++)
		scanf("%s",map[i]);
	for(i = 0; i < r; i++)
	{
		for(j = 0; j < c; j++)
		{
			if(map[i][j]=='S')
				pi = i,pj = j,map[i][j]='.';
			if(map[i][j]=='B')
				bi = i,bj = j,map[i][j]='.';
			if(map[i][j]=='T')
				ti = i,tj = j,map[i][j]='.';
		}
	}
	memset(mark,0,sizeof(mark));
	solve();
	printf("\n");
}

int main()
{
	int cas = 0;

	while(scanf("%d%d",&r,&c)==2&&r)
	{
		printf("Maze #%d\n",++cas);
		input();
	}
	return 1;
}