2254900_wa.cpp

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

# include <iostream>
# include <string>

using namespace std;

int a, c, d, b;
int i, j, ei, ej;
int mark[7][7][5];

typedef struct node
{
	int l;
	int r, c;
	char way[100];
}W;

void bfs()
{
	W queue[100];
	int f, r, l, t;
	int tr, tc;
	int flag[7][7];

	memset(flag,0,sizeof(flag));
	flag[i][j] = 1;
	f = r = -1;
	queue[0].r = i;
	queue[0].c = j;
	queue[0].l = 0;
	f++;
	while(f!=r)
	{
		r++;
		tr = queue[r].r;tc = queue[r].c;l = queue[r].l;
		if(tr==ei&&tc==ej)
		{
			for(t = 0; t < l; t++)
				printf("%c",queue[r].way[t]);
			printf("\n");
			break;
		}
		if(tr>1&&flag[tr-1][tc]==0&&mark[tr][tc][0]==0)
		{
			flag[tr-1][tc] = 1;
			queue[++f].r = tr-1;
			queue[f].c = tc;
			for(t = 0; t < l; t++)
				queue[f].way[t] = queue[r].way[t];
			queue[f].way[t] = 'N';
			queue[f].l = t+1;
		}
		if(tc>1&&flag[tr][tc-1]==0&&mark[tr][tc][2]==0)
		{
			flag[tr][tc-1] = 1;
			queue[++f].r = tr;
			queue[f].c = tc-1;
			for(t = 0; t < l; t++)
				queue[f].way[t] = queue[r].way[t];
			queue[f].way[t] = 'W';
			queue[f].l = t+1;
		}
		if(tr<6&&flag[tr+1][tc]==0&&mark[tr][tc][1]==0)
		{
			flag[tr+1][tc] = 1;
			queue[++f].r = tr+1;
			queue[f].c = tc;
			for(t = 0; t < l; t++)
				queue[f].way[t] = queue[r].way[t];
			queue[f].way[t] = 'S';
			queue[f].l = t+1;
		}
		if(tc<6&&flag[tr][tc+1]==0&&mark[tr][tc][3]==0)
		{
			flag[tr][tc+1] = 1;
			queue[++f].r = tr;
			queue[f].c = tc+1;
			for(t = 0; t < l; t++)
				queue[f].way[t] = queue[r].way[t];
			queue[f].way[t] = 'E';
			queue[f].l = t+1;
		}
	}
}

void input()
{
	int n, m;

	while(scanf("%d%d",&j,&i)==2&&i&&j)
	{
		scanf("%d%d",&ej,&ei);
		memset(mark,0,sizeof(mark));
		for(n = 1; n <= 3; n++)
		{
			scanf("%d%d%d%d",&a,&b,&c,&d);
			if(b==d)
				for(m = a; m < c; m++)
					mark[b+1][m+1][0] = 1, mark[b][m+1][1] = 1;
			else
				for(m = b; m < d; m++)
					mark[m+1][a][3] = 1, mark[m+1][a+1][2] = 1;
		}
		bfs();
	}
}

int main()
{
	input();
	return 1;
}