POJ 2251 Dungeon Master

题目链接：POJ 2251 Dungeon Master

题目大意：
你被困在一个3D地牢中且继续寻找最短路径逃生，地牢由立方体单位构成，立方体单位中有的会充满岩石。向上下前后左右移动一个单位需要一分钟。你不能向对角线的四个方向移动且迷宫四周环绕着许多岩石。是否可以逃出地牢？如果可以，则需要多少时间？

题解：
用BFS遍历六个方向。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define ms(a, b) memset(a, b, sizeof(a))
#define ll long long
#define io_speed_up ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
#define MAXN 35

char ch;
int mat[MAXN][MAXN][MAXN];
int sx, sy, sz, tx, ty, tz;
int l, r, c;
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
int ans;
struct node {
	int x, y, z, step;
};

int bfs() {
	queue <node> q;
	q.push(node{sx, sy, sz, 0});
	mat[sx][sy][sz] = 0;
	while (!q.empty()) {
		node t = q.front();
		q.pop();
		for (int i = 0; i < 6; ++i) {
			int nx = t.x + dx[i];
			int ny = t.y + dy[i];
			int nz = t.z + dz[i];
			if (nx == tx && ny == ty && nz == tz) {
				return t.step + 1;
			}
			if (mat[nx][ny][nz]) {
				mat[nx][ny][nz] = 0;
				q.push(node{nx, ny, nz, t.step + 1});
			}
		}
	}
	return INF;
}

int main() {
	io_speed_up;
	while (cin >> l >> r >> c) {
		if (!l && !r && !c) break;
		ans = INF;
		ms(mat, 0);
		for (int i = 1; i <= l; ++i) {
			for (int j = 1; j <= r; ++j) {
				for (int k = 1; k <= c; ++k) {
					cin >> ch;
					if (ch == 'S') {
						sx = i, sy = j, sz = k;
						mat[i][j][k] = 1;
					} else if (ch == 'E') {
						tx = i, ty = j, tz = k;
						mat[i][j][k] = 1;
					} else if (ch == '#') {
						mat[i][j][k] = 0;
					} else {
						mat[i][j][k] = 1;
					}
				}
			}
		}
		ans = bfs();
		if (ans == INF) {
			cout << "Trapped!" << endl;
		} else {
			cout << "Escaped in " << ans << " minute(s)." << endl;
		}
	}
	return 0; 
}