三维迷宫

问题描述

zjm 被困在一个三维的空间中, 现在要寻找最短路径逃生！
空间由立方体单位构成。
zjm 每次向上下前后左右移动一个单位需要一分钟，且 zjm 不能对角线移动。
空间的四周封闭。zjm 的目标是走到空间的出口。
是否存在逃出生天的可能性？如果存在，则需要多少时间？

Input

输入第一行是一个数表示空间的数量。
每个空间的描述的第一行为 L, R 和 C（皆不超过 30）。
L 表示空间的高度，R 和 C 分别表示每层空间的行与列的大小。
随后 L 层，每层 R 行，每行 C 个字符。
每个字符表示空间的一个单元。'#' 表示不可通过单元，'.' 表示空白单元。
zjm 的起始位置在 'S'，出口为 'E'。每层空间后都有一个空行。
L, R 和 C 均为 0 时输入结束。

Output

每个空间对应一行输出。
如果可以逃生，则输出如下
Escaped in x minute(s).
x 为最短脱离时间。

如果无法逃生，则输出如下
Trapped!

Sample

Input: 
3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0


Output: 
Escaped in 11 minute(s).
Trapped!

Limitation

Time limit      1000 ms
Memory limit    262144 kb

解题思路

三维空间的广搜，每次上下左右前后考虑，记录搜索路径，输出步数，没啥坑。

源代码

#include <iostream>
#include <queue>
using namespace std;

struct coordinate {
	int x, y, z;
	coordinate() { x = 0; y = 0; z = 0; }
	coordinate(int _x, int _y, int _z) :x(_x), y(_y), z(_z) {  }
	coordinate(const coordinate& c) {
		x = c.x;
		y = c.y;
		z = c.z;
	}
	bool operator!=(const coordinate& C) {
		return (x != C.x || y != C.y || z != C.z);
	}
	bool operator==(const coordinate& C) {
		return (x == C.x || y == C.y || z == C.z);
	}
};

const int maxN = 35;
char room[maxN][maxN][maxN];

int dX[] = { -1,1,0,0,0,0 };
int dY[] = { 0,0,-1,1,0,0 };
int dZ[] = { 0,0,0,0,-1,1 };

int maze(int l, int r, int c, coordinate S, coordinate E) {
	bool reached[maxN][maxN][maxN] = { false };
	queue<coordinate> q;
	queue<int> steps;
	q.push(S);
	steps.push(0);
	while (!q.empty()) {
		coordinate cur = q.front();
		q.pop();
		int stp = steps.front();
		steps.pop();
		int cx = cur.x, cy = cur.y, cz = cur.z;
		for (int i = 0; i < 6; i++) {
			int tx = cx + dX[i];
			int ty = cy + dY[i];
			int tz = cz + dZ[i];
			if (tx >= 0 && ty >= 0 && tz >= 0 &&
				tx < l && ty < r && tz < c &&
				!reached[tx][ty][tz] &&
				room[tx][ty][tz] != '#') {
				reached[tx][ty][tz] = true;
				if (room[tx][ty][tz] == 'E') {
					return (stp + 1);
					break;
				}
				coordinate tempC(tx, ty, tz);
				q.push(tempC);
				steps.push(stp + 1);
			}
		}
	}
	return 0;
}

int main() {
	int l, r, c;
	while (!(cin >> l >> r >> c).eof()) {
		if (l == 0 && r == 0 && c == 0)
			break;
		coordinate st, ed;
		for (int i = 0; i < l; i++)
			for (int j = 0; j < r; j++)
				for (int k = 0; k < c; k++) {
					cin >> room[i][j][k];
					if (room[i][j][k] == 'S') {
						coordinate tempC(i, j, k);
						st = tempC;
					}
					if (room[i][j][k] == 'E') {
						coordinate tempC(i, j, k);
						ed = tempC;
					}
				}
		int res = maze(l, r, c, st, ed);
		if (res != 0)
			cout << "Escaped in " << res << " minute(s)." << endl;
		else
			cout << "Trapped!" << endl;
	}

	return 0;
}