1422.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1422 on 2006-01-10 at 18:57:58 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 16;
typedef struct pair<int, int> pii;

char map[MAX][MAX][MAX];
int x, y, z;
int n;

inline int code(int, int, int);
inline void decode(int);
inline bool can(int, int, int);

int main()
{
	int i, j;
	int bx, by, bz, ex, ey, ez;
	bool visit[MAX][MAX][MAX];
	queue<pii> Q;
	
	while(scanf("%*s %d", &n) != EOF) {
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				scanf("%s", map[i][j]);
		memset(visit, false, sizeof(visit));
		while(!Q.empty()) Q.pop();
		scanf("%d %d %d", &bz, &by, &bx);
		scanf("%d %d %d", &ez, &ey, &ex);
		int b = code(bx, by, bz), e = code(ex, ey, ez);
		Q.push(pii(b, 0)); visit[bx][by][bz] = true;
		int time = -1;
		if(b == e) time = 0;
		else {
			map[ex][ey][ez] = 'E';
			while(!Q.empty()) {
				pii t = Q.front(); Q.pop();
				decode(t.first);
				if(can(x-1, y, z))
					if(map[x-1][y][z] == 'E') { time = t.second+1; break; }
					else if(!visit[x-1][y][z]) visit[x-1][y][z] = true, Q.push(pii(code(x-1, y, z), t.second+1));
				if(can(x+1, y, z))
					if(map[x+1][y][z] == 'E') { time = t.second+1; break; }
					else if(!visit[x+1][y][z]) visit[x+1][y][z] = true, Q.push(pii(code(x+1, y, z), t.second+1));
				if(can(x, y-1, z))
					if(map[x][y-1][z] == 'E') { time = t.second+1; break; }
					else if(!visit[x][y-1][z]) visit[x][y-1][z] = true, Q.push(pii(code(x, y-1, z), t.second+1));
				if(can(x, y+1, z))
					if(map[x][y+1][z] == 'E') { time = t.second+1; break; }
					else if(!visit[x][y+1][z]) visit[x][y+1][z] = true, Q.push(pii(code(x, y+1, z), t.second+1));
				if(can(x, y, z-1))
					if(map[x][y][z-1] == 'E') { time = t.second+1; break; }
					else if(!visit[x][y][z-1]) visit[x][y][z-1] = true, Q.push(pii(code(x, y, z-1), t.second+1));
				if(can(x, y, z+1))
					if(map[x][y][z+1] == 'E') { time = t.second+1; break; }
					else if(!visit[x][y][z+1]) visit[x][y][z+1] = true, Q.push(pii(code(x, y, z+1), t.second+1));
			}
		}
		if(time == -1) printf("NO ROUTE\n");
		else printf("%d %d\n", n, time);
		scanf("%*s");
	}
	
	return 0;
}

inline int code(int a, int b, int n)
{
	return a*MAX*MAX + b*MAX + n;
}
inline void decode(int m)
{
	x = m / (MAX*MAX);
	y = m % (MAX*MAX) / MAX;
	z = m % MAX;
}
inline bool can(int x, int y, int z)
{
	if(x < 0 || x >= n || y < 0 || y >= n || z < 0 || z >= n) return false;
	else if(map[x][y][z] == 'X') return false;
	else return true;
}