2447144_ac_1390ms_16968k.c

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

#include <stdio.h>
#include <string.h>
int r, c;
char map[501][501];

struct node
{
	int dir;
	int id;
	int x, y;
	int way;
}queue[1000000];
int f, p;
int dx, dy;
int single[501][501], twins[501][501][5];

void bfs()//1 up 2 left 3 down 4 right
{
	int way, dir, id, x, y;

	while(f!=p)
	{
		++p;
		id = queue[p].id;dir = queue[p].dir;way = queue[p].way;
		x = queue[p].x;y = queue[p].y;
		if(id==1)
		{
			if(map[x-1][y]=='.'&&map[x-2][y]=='.'&&!twins[x-1][y][1])
			{
				twins[x-1][y][1] = twins[x-2][y][3] = 1;
				++f;
				queue[f].id = 2;queue[f].way = way+1;queue[f].dir = 1;
				queue[f].x = x-1,queue[f].y = y;
			}
			if(map[x][y-1]=='.'&&map[x][y-2]=='.'&&!twins[x][y-1][2])
			{
				twins[x][y-1][2] = twins[x][y-2][4] = 1;
				++f;
				queue[f].id = 2;queue[f].way = way+1;queue[f].dir = 2;
				queue[f].x = x,queue[f].y = y-1;
			}
			if(map[x+1][y]=='.'&&map[x+2][y]=='.'&&!twins[x+1][y][3])
			{
				twins[x+1][y][3] = twins[x+2][y][1] = 1;
				++f;
				queue[f].id = 2;queue[f].way = way+1;queue[f].dir = 3;
				queue[f].x = x+1,queue[f].y = y;
			}
			if(map[x][y+1]=='.'&&map[x][y+2]=='.'&&!twins[x][y+1][4])
			{
				twins[x][y+1][4] = twins[x][y+2][2] = 1;
				++f;
				queue[f].id = 2;queue[f].way = way+1;queue[f].dir = 4;
				queue[f].x = x,queue[f].y = y+1;
			}
		}
		else
		{
			if(dir==1)
			{
				if(map[x][y-1]=='.'&&map[x-1][y-1]=='.'&&!twins[x][y-1][1])
				{
					++f;
					twins[x][y-1][1] = twins[x-1][y-1][3] = 1;
					queue[f].id = 2;queue[f].way = way+1;queue[f].dir = 1;
					queue[f].x = x;queue[f].y = y-1;
				}
				if(map[x][y+1]=='.'&&map[x-1][y+1]=='.'&&!twins[x][y+1][1])
				{
					++f;
					twins[x][y+1][1] = twins[x-1][y+1][3] = 1;
					queue[f].id = 2;queue[f].way = way+1;queue[f].dir = 1;
					queue[f].x = x;queue[f].y = y+1;
				}
				if(map[x+1][y]=='.'&&!single[x+1][y])
				{
					single[x+1][y] = 1;
					++f;
					queue[f].id = 1;queue[f].way = way+1;
					queue[f].x = x+1;queue[f].y = y;
					if(x+1==dx&&y==dy)
					{
						printf("%d\n",way+1);
						return ;
					}
				}
				if(map[x-2][y]=='.'&&!single[x-2][y])
				{
					single[x-2][y] = 1;
					++f;
					queue[f].id = 1;queue[f].way = way+1;
					queue[f].x = x-2;queue[f].y = y;
					if(x-2==dx&&y==dy)
					{
						printf("%d\n",way+1);
						return ;
					}
				}
			}
			if(dir==2)
			{
				if(map[x-1][y]=='.'&&map[x-1][y-1]=='.'&&!twins[x-1][y][2])
				{
					++f;
					twins[x-1][y][2] = twins[x-1][y-1][4] = 1;
					queue[f].id = 2;queue[f].way = way+1;queue[f].dir = 2;
					queue[f].x = x-1;queue[f].y = y;
				}
				if(map[x+1][y]=='.'&&map[x+1][y-1]=='.'&&!twins[x+1][y][2])
				{
					++f;
					twins[x+1][y][2] = twins[x+1][y-1][4] = 1;
					queue[f].id = 2;queue[f].way = way+1;queue[f].dir = 2;
					queue[f].x = x+1;queue[f].y = y;
				}
				if(map[x][y+1]=='.'&&!single[x][y+1])
				{
					single[x][y+1] = 1;
					++f;
					queue[f].id = 1;queue[f].way = way+1;
					queue[f].x = x;queue[f].y = y+1;
					if(x==dx&&y+1==dy)
					{
						printf("%d\n",way+1);
						return ;
					}
				}
				if(map[x][y-2]=='.'&&!single[x][y-2])
				{
					single[x][y-2] = 1;
					++f;
					queue[f].id = 1;queue[f].way = way+1;
					queue[f].x = x;queue[f].y = y-2;
					if(x==dx&&y-2==dy)
					{
						printf("%d\n",way+1);
						return ;
					}
				}
			}
			if(dir==3)
			{
				if(map[x][y-1]=='.'&&map[x+1][y-1]=='.'&&!twins[x][y-1][3])
				{
					++f;
					twins[x][y-1][3] = twins[x+1][y-1][1] = 1;
					queue[f].id = 2;queue[f].way = way+1;queue[f].dir = 3;
					queue[f].x = x;queue[f].y = y-1;
				}
				if(map[x][y+1]=='.'&&map[x+1][y+1]=='.'&&!twins[x][y+1][3])
				{
					++f;
					twins[x][y+1][3] = twins[x+1][y+1][1] = 1;
					queue[f].id = 2;queue[f].way = way+1;queue[f].dir = 3;
					queue[f].x = x;queue[f].y = y+1;
				}
				if(map[x-1][y]=='.'&&!single[x-1][y])
				{
					single[x-1][y] = 1;
					++f;
					queue[f].id = 1;queue[f].way = way+1;
					queue[f].x = x-1;queue[f].y = y;
					if(x-1==dx&&y==dy)
					{
						printf("%d\n",way+1);
						return ;
					}
				}
				if(map[x+2][y]=='.'&&!single[x+2][y])
				{
					single[x+2][y] = 1;
					++f;
					queue[f].id = 1;queue[f].way = way+1;
					queue[f].x = x+2;queue[f].y = y;
					if(x+2==dx&&y==dy)
					{
						printf("%d\n",way+1);
						return ;
					}
				}
			}
			if(dir==4)
			{
				if(map[x-1][y]=='.'&&map[x-1][y+1]=='.'&&!twins[x-1][y][4])
				{
					++f;
					twins[x-1][y][4] = twins[x-1][y+1][2] = 1;
					queue[f].id = 2;queue[f].way = way+1;queue[f].dir = 4;
					queue[f].x = x-1;queue[f].y = y;
				}
				if(map[x+1][y]=='.'&&map[x+1][y+1]=='.'&&!twins[x+1][y][4])
				{
					++f;
					twins[x+1][y][4] = twins[x+1][y+1][2] = 1;
					queue[f].id = 2;queue[f].way = way+1;queue[f].dir = 4;
					queue[f].x = x+1;queue[f].y = y;
				}
				if(map[x][y-1]=='.'&&!single[x][y-1])
				{
					single[x][y-1] = 1;
					++f;
					queue[f].id = 1;queue[f].way = way+1;
					queue[f].x = x;queue[f].y = y-1;
					if(x==dx&&y-1==dy)
					{
						printf("%d\n",way+1);
						return ;
					}
				}
				if(map[x][y+2]=='.'&&!single[x][y+2])
				{
					single[x][y+2] = 1;
					++f;
					queue[f].id = 1;queue[f].way = way+1;
					queue[f].x = x;queue[f].y = y+2;
					if(x==dx&&y+2==dy)
					{
						printf("%d\n",way+1);
						return ;
					}
				}
			}
		}
	}
	printf("Impossible\n");
}

int main()
{
	int i, j;

	while(scanf("%d%d",&r,&c)==2)
	{
		if(r==0&&r==c)
			break;
		f = p = -1;
		memset(single,0,sizeof(single));
		memset(twins,0,sizeof(twins));
		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]=='E')
					map[i][j] = '.',single[i][j] = 1;
				if(map[i][j]=='O')
				{
					map[i][j] = '.';
					dx = i;dy = j;
				}
			}
		for(i = 0; i < r; i++)
			for(j = 0; j < c; j++)
				if(map[i][j]=='X')
				{
					map[i][j] = '.';
					f++;queue[f].way = 0;queue[f].x = i,queue[f].y = j;queue[f].id = 2;
					if(map[i-1][j]=='X')
					{
						map[i-1][j] = '.';
						queue[f].dir = 1;
						twins[i][j][1] = 1;
						twins[i-1][j][1] = 3;
						goto con;
					}
					if(map[i][j-1]=='X')
					{
						map[i][j-1] = '.';
						queue[f].dir = 2;
						twins[i][j][2] = 1;
						twins[i][j-1][4] = 1;
						goto con;
					}
					if(map[i+1][j]=='X')
					{
						map[i+1][j] = '.';
						queue[f].dir = 3;
						twins[i][j][3] = 1;
						twins[i+1][j][1] = 1;
						goto con;
					}
					if(map[i][j+1]=='X')
					{
						map[i][j+1] = '.';
						queue[f].dir = 4;
						twins[i][j][4] = 1;
						twins[i][j+1][2] = 1;
						goto con;
					}
					queue[f].id = 1;
					single[i][j] = 1;
				}
con:
		bfs();
	}
	return 1;
}