PKU 2251 Dungeon Master

• 三次元の幅優先探索
• 広げる方向は6方向

static const int dx[] = {1, -1, 0, 0, 0, 0};
static const int dy[] = {0, 0, 1, -1, 0, 0};
static const int dz[] = {0, 0, 0, 0, 1, -1};

int main() {
	for (int X, Y, Z; cin >> X >> Y >> Z && (X || Y || Z); ) {
		static char maze[32][32][32];
		memset(maze, '#', sizeof(maze));
		static int dp[32][32][32];
		memset(dp, 0, sizeof(dp));

		int startX, startY, startZ, goalX, goalY, goalZ;

		for (int x = 1; x <= X; ++x) {
			for (int y = 1; y <= Y; ++y) {
				for (int z = 1; z <= Z; ++z) {
					cin >> maze[x][y][z];

					if (maze[x][y][z] == 'S') {
						startX = x;
						startY = y;
						startZ = z;
					} else if (maze[x][y][z] == 'E') {
						goalX = x;
						goalY = y;
						goalZ = z;
					}
				}
			}
		}

		deque<int> q;
		q.push_back(startX);
		q.push_back(startY);
		q.push_back(startZ);
		dp[startX][startY][startZ] = 1;

		while (!q.empty()) {
			const int x = q.front();
			q.pop_front();
			const int y = q.front();
			q.pop_front();
			const int z = q.front();
			q.pop_front();

			for (int dir = 0; dir < 6; ++dir) {
				const int nextX = x + dx[dir];
				const int nextY = y + dy[dir];
				const int nextZ = z + dz[dir];

				if (dp[nextX][nextY][nextZ] || maze[nextX][nextY][nextZ] == '#') {
					continue;
				}
				dp[nextX][nextY][nextZ] = dp[x][y][z] + 1;

				q.push_back(nextX);
				q.push_back(nextY);
				q.push_back(nextZ);
			}
		}

		if (dp[goalX][goalY][goalZ]) {
			printf("Escaped in %d minute(s).\n", dp[goalX][goalY][goalZ] - 1);
		} else {
			printf("Trapped!\n");
		}
	}
}