题目描述
Ada\\texttt{Ada}Ada 发现了一个名为“多楼层迷宫”的旧游戏。游戏由一个多层迷宫组成，每层迷宫是一个由道路和墙壁构成的网格，并且层与层之间通过电梯连接。起点 SSS 和终点 EEE 可能位于任意楼层。
Ada\\texttt{Ada}Ada 每次可以向六个方向移动一步：北、南、东、西、上一层或下一层 。电梯的使用规则是：只有当相邻楼层在完全相同的位置也有电梯（字符 – ）时，才能通过电梯上下楼。电梯本身也可以当作普通道路使用，即 Ada\\texttt{Ada}Ada 可以停留在电梯位置而不换层。
迷宫表示方法如下：
- # 表示墙壁，不可通行。
- . 表示可通行的空地。
- – 表示电梯，可通行，并允许在满足条件时上下楼。
- S 表示起点，唯一。
- E 表示终点，唯一。
目标 ：计算从起点到终点的最少步数 ，若无法到达则输出 −1-1−1 。
输入格式
输入包含多个测试用例，每个测试用例格式如下：
l w h
floor1
floor2
…
floorh
- lll ：每层的行数 （ 1≤l≤1001 \\le l \\le 1001≤l≤100 ）。
- www ：每层的列数 （ 1≤w≤1001 \\le w \\le 1001≤w≤100 ）。
- hhh ：楼层数（ 1≤h≤1001 \\le h \\le 1001≤h≤100 ）。
接下来描述 hhh 个楼层，从第 111 层到第 hhh 层 。每个楼层由 lll 行字符串组成，每行包含 www 个字符，符合上述符号约定。保证每个测试用例中只有一个 SSS 和一个 EEE 。每个楼层描述后有一个空行（样例中可能省略，但题目说明中存在）。
输入以 0 0 0 结束。
输出格式
对于每个测试用例，输出一行，表示从起点到终点的最少步数；若不可达，输出 −1-1−1 。
题目分析
问题本质
这是一个三维迷宫最短路径问题 ，可以建模为无权图上的单源最短路径 。每个状态是一个三元组 (x,y,z)(x, y, z)(x,y,z) ，表示位于第 zzz 层、第 xxx 行、第 yyy 列的格子。目标是找到从起点状态到终点状态的最短路径长度。
核心难点
- 同一层内可向四个方向移动（上、下、左、右）。
- 通过电梯上下楼时，要求当前格子和目标楼层的对应格子都是电梯（ – ）。
解题思路
由于边权均为 111 （每移动一步代价相同），可以使用 BFS\\texttt{BFS}BFS（广度优先搜索） 求解最短路径。
算法步骤 ：
- 四方向移动 ：在同一层内向上、下、左、右移动，若目标位置不是墙壁且未访问，则更新距离并入队。
- 电梯移动 ：若当前位置是电梯（ – ），则检查相邻楼层（上一层和下一层）的同一位置是否也是电梯。若是，则移动到对应楼层，更新距离并入队。
时间复杂度 ：每个状态最多入队一次，每次扩展最多 666 个方向（ 444 个平面方向 + 222 个电梯方向）。总复杂度 O(l×w×h)O(l \\times w \\times h)O(l×w×h) ，在 1003=106100^3 = 10^61003=106 范围内可接受。
空间复杂度 ：需要存储迷宫和距离数组，均为 O(l×w×h)O(l \\times w \\times h)O(l×w×h) 。
代码实现
// Multistory Labyrinth
// UVa ID: 13116
// Verdict: Accepted
// Submission Date: 2026-01-26
// UVa Run Time: 0.100s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105; // 最大维度
struct Point {
int x, y, z; // x:行, y:列, z:层
Point(int x, int y, int z) : x(x), y(y), z(z) {}
};
// 方向数组：dx 表示行变化，dy 表示列变化
int dx[] = {1, –1, 0, 0, 0, 0}, dy[] = {0, 0, 1, –1, 0, 0};
char grid[MAXN][MAXN][MAXN]; // 存储迷宫：[层][行][列]
int dist[MAXN][MAXN][MAXN]; // 存储距离：[层][行][列]
int bfs(Point start, Point end, int l, int w, int h) {
// 初始化距离为 -1（未访问）
memset(dist, –1, sizeof dist);
queue<Point> q;
dist[start.z][start.x][start.y] = 0;
q.push(start);
while (!q.empty()) {
Point p = q.front(); q.pop();
// 到达终点，返回最短步数
if (p.x == end.x && p.y == end.y && p.z == end.z)
return dist[p.z][p.x][p.y];
// 四方向移动（同一层内）
for (int i = 0; i < 4; i++) {
int nx = p.x + dx[i], ny = p.y + dy[i], nz = p.z;
if (nx >= 0 && nx < l && ny >= 0 && ny < w && nz >= 0 && nz < h) {
if (grid[nz][nx][ny] != '#' && dist[nz][nx][ny] == –1) {
dist[nz][nx][ny] = dist[p.z][p.x][p.y] + 1;
q.push(Point(nx, ny, nz));
}
}
}
// 电梯上下移动
if (grid[p.z][p.x][p.y] == '-') {
for (int dz : {1, –1}) { // 上楼和下楼
int nz = p.z + dz;
if (nz >= 0 && nz < h && grid[nz][p.x][p.y] == '-') {
if (dist[nz][p.x][p.y] == –1) {
dist[nz][p.x][p.y] = dist[p.z][p.x][p.y] + 1;
q.push(Point(p.x, p.y, nz));
}
}
}
}
}
return –1; // 无法到达终点
}
int main() {
int l, w, h;
while (cin >> l >> w >> h) {
if (l == 0 && w == 0 && h == 0) break;
Point start(0, 0, 0), end(0, 0, 0);
// 读取 h 层，每层 l 行，每行 w 个字符
for (int k = 0; k < h; k++) {
for (int i = 0; i < l; i++) { // 每层有 l 行
string line;
cin >> line;
for (int j = 0; j < w; j++) { // 每行有 w 列
grid[k][i][j] = line[j];
if (line[j] == 'S') start = Point(i, j, k); // 记录起点
if (line[j] == 'E') end = Point(i, j, k); // 记录终点
}
}
}
int r = bfs(start, end, l, w, h);
cout << r << endl;
}
return 0;
}
代码要点解析
样例分析
样例输入 1
4 4 3
S..-
#.##
..#-
-#E.
…-
.###
.#.-
-#..
.#.-
.#.#
.#.-
…#
输出 ： 131313
解释：如题目图示，需要 131313 步从起点到达终点，中间可能多次换层。
样例输入 2
2 4 2
.-..
….
S–E
####
输出 ： 333
解释：起点和终点在同一层，直接向右移动 333 步即可到达，无需使用电梯。
总结
本题是三维 BFS\\texttt{BFS}BFS 的经典应用，主要考察对状态空间的理解和 BFS\\texttt{BFS}BFS 的实现能力。关键点在于正确处理电梯移动规则（必须两端都是电梯）以及使用 BFS\\texttt{BFS}BFS 保证首次到达即为最短路径。代码实现时需要注意数组维度的顺序和边界条件的检查。
