1448.cpp

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

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

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

char map[MAX][MAX][MAX];
int x, y, z;
int l, r, c, b;

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

int main()
{
	
	int i, j, k;
	bool visit[MAX][MAX][MAX];
	queue<pii> Q;
	
	while(scanf("%d %d %d", &l, &r, &c) != EOF && l*r*c != 0) {
		for(i = 0; i < l; i++)
			for(j = 0; j < r; j++) {
				scanf("%s", map[i][j]);
				for(k = 0; k < c; k++)
					if(map[i][j][k] == 'S') b = code(i, j, k);
			}
		memset(visit, false, sizeof(visit));
		while(!Q.empty()) Q.pop();
		Q.push(pii(b, 0));
		decode(b); visit[x][y][z] = true;
		int time = -1;
		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("Trapped!\n");
		else printf("Escaped in %d minute(s).\n", time);
	}
	
	return 0;
}

inline int code(int a, int b, int c)
{
	return a*MAX*MAX + b*MAX + c;
}
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 >= l || y < 0 || y >= r || z < 0 || z >= c) return false;
	else if(map[x][y][z] == '#') return false;
	else return true;
}