题目描述Ada\texttt{Ada}Ada发现了一个名为“多楼层迷宫”的旧游戏。游戏由一个多层迷宫组成每层迷宫是一个由道路和墙壁构成的网格并且层与层之间通过电梯连接。起点SSS和终点EEE可能位于任意楼层。Ada\texttt{Ada}Ada每次可以向六个方向移动一步北、南、东、西、上一层或下一层。电梯的使用规则是只有当相邻楼层在完全相同的位置也有电梯字符-时才能通过电梯上下楼。电梯本身也可以当作普通道路使用即Ada\texttt{Ada}Ada可以停留在电梯位置而不换层。迷宫表示方法如下#表示墙壁不可通行。.表示可通行的空地。-表示电梯可通行并允许在满足条件时上下楼。S表示起点唯一。E表示终点唯一。目标计算从起点到终点的最少步数若无法到达则输出−1-1−1。输入格式输入包含多个测试用例每个测试用例格式如下l w h floor1 floor2 ... floorhlll每层的行数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列的格子。目标是找到从起点状态到终点状态的最短路径长度。核心难点状态空间较大最多100×100×100106100 \times 100 \times 100 10^6100×100×100106个状态需要使用高效的搜索算法。移动规则复杂同一层内可向四个方向移动上、下、左、右。通过电梯上下楼时要求当前格子和目标楼层的对应格子都是电梯-。路径可能存在循环例如先上楼再下楼再上楼可能形成更短的路径因此不能简单使用DFS\texttt{DFS}DFS而应使用BFS\texttt{BFS}BFS保证首次到达即为最短。解题思路由于边权均为111每移动一步代价相同可以使用BFS\texttt{BFS}BFS广度优先搜索求解最短路径。算法步骤状态表示使用结构体Point存储(x,y,z)(x, y, z)(x,y,z)分别表示行、列、层。距离记录使用三维数组dist[z][x][y]记录从起点到该状态的最短步数初始化为−1-1−1表示未访问。BFS\texttt{BFS}BFS队列将起点状态加入队列距离设为000。状态扩展对于队列中的每个状态尝试所有可能的移动四方向移动在同一层内向上、下、左、右移动若目标位置不是墙壁且未访问则更新距离并入队。电梯移动若当前位置是电梯-则检查相邻楼层上一层和下一层的同一位置是否也是电梯。若是则移动到对应楼层更新距离并入队。终止条件当访问到终点状态时立即返回其距离若队列空仍未访问到终点返回−1-1−1。时间复杂度每个状态最多入队一次每次扩展最多666个方向444个平面方向 222个电梯方向。总复杂度O(l×w×h)O(l \times w \times h)O(l×w×h)在1003106100^3 10^61003106范围内可接受。空间复杂度需要存储迷宫和距离数组均为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//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN105;// 最大维度structPoint{intx,y,z;// x:行, y:列, z:层Point(intx,inty,intz):x(x),y(y),z(z){}};// 方向数组dx 表示行变化dy 表示列变化intdx[]{1,-1,0,0,0,0},dy[]{0,0,1,-1,0,0};chargrid[MAXN][MAXN][MAXN];// 存储迷宫[层][行][列]intdist[MAXN][MAXN][MAXN];// 存储距离[层][行][列]intbfs(Point start,Point end,intl,intw,inth){// 初始化距离为 -1未访问memset(dist,-1,sizeofdist);queuePointq;dist[start.z][start.x][start.y]0;q.push(start);while(!q.empty()){Point pq.front();q.pop();// 到达终点返回最短步数if(p.xend.xp.yend.yp.zend.z)returndist[p.z][p.x][p.y];// 四方向移动同一层内for(inti0;i4;i){intnxp.xdx[i],nyp.ydy[i],nzp.z;if(nx0nxlny0nywnz0nzh){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(intdz:{1,-1}){// 上楼和下楼intnzp.zdz;if(nz0nzhgrid[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;// 无法到达终点}intmain(){intl,w,h;while(cinlwh){if(l0w0h0)break;Pointstart(0,0,0),end(0,0,0);// 读取 h 层每层 l 行每行 w 个字符for(intk0;kh;k){for(inti0;il;i){// 每层有 l 行string line;cinline;for(intj0;jw;j){// 每行有 w 列grid[k][i][j]line[j];if(line[j]S)startPoint(i,j,k);// 记录起点if(line[j]E)endPoint(i,j,k);// 记录终点}}}intrbfs(start,end,l,w,h);coutrendl;}return0;}代码要点解析数组维度使用grid[z][x][y]和dist[z][x][y]表示第zzz层第xxx行第yyy列的状态。注意坐标顺序层、行、列。BFS\texttt{BFS}BFS初始化使用memset(dist, -1, sizeof dist)快速初始化距离数组。电梯移动条件仅当grid[p.z][p.x][p.y] -且相邻楼层的相同位置也是-时才允许上下楼。边界检查移动时检查新位置是否在迷宫范围内。输入处理由于题目保证每行长度正确直接按行读取即可。样例分析样例输入 14 4 3 S..- #.## ..#- -#E. ...- .### .#.- -#.. .#.- .#.# .#.- ...#输出131313解释如题目图示需要131313步从起点到达终点中间可能多次换层。样例输入 22 4 2 .-.. .... S--E ####输出333解释起点和终点在同一层直接向右移动333步即可到达无需使用电梯。总结本题是三维BFS\texttt{BFS}BFS的经典应用主要考察对状态空间的理解和BFS\texttt{BFS}BFS的实现能力。关键点在于正确处理电梯移动规则必须两端都是电梯以及使用BFS\texttt{BFS}BFS保证首次到达即为最短路径。代码实现时需要注意数组维度的顺序和边界条件的检查。
UVa 13116 Multistory Labyrinth
题目描述Ada\texttt{Ada}Ada发现了一个名为“多楼层迷宫”的旧游戏。游戏由一个多层迷宫组成每层迷宫是一个由道路和墙壁构成的网格并且层与层之间通过电梯连接。起点SSS和终点EEE可能位于任意楼层。Ada\texttt{Ada}Ada每次可以向六个方向移动一步北、南、东、西、上一层或下一层。电梯的使用规则是只有当相邻楼层在完全相同的位置也有电梯字符-时才能通过电梯上下楼。电梯本身也可以当作普通道路使用即Ada\texttt{Ada}Ada可以停留在电梯位置而不换层。迷宫表示方法如下#表示墙壁不可通行。.表示可通行的空地。-表示电梯可通行并允许在满足条件时上下楼。S表示起点唯一。E表示终点唯一。目标计算从起点到终点的最少步数若无法到达则输出−1-1−1。输入格式输入包含多个测试用例每个测试用例格式如下l w h floor1 floor2 ... floorhlll每层的行数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列的格子。目标是找到从起点状态到终点状态的最短路径长度。核心难点状态空间较大最多100×100×100106100 \times 100 \times 100 10^6100×100×100106个状态需要使用高效的搜索算法。移动规则复杂同一层内可向四个方向移动上、下、左、右。通过电梯上下楼时要求当前格子和目标楼层的对应格子都是电梯-。路径可能存在循环例如先上楼再下楼再上楼可能形成更短的路径因此不能简单使用DFS\texttt{DFS}DFS而应使用BFS\texttt{BFS}BFS保证首次到达即为最短。解题思路由于边权均为111每移动一步代价相同可以使用BFS\texttt{BFS}BFS广度优先搜索求解最短路径。算法步骤状态表示使用结构体Point存储(x,y,z)(x, y, z)(x,y,z)分别表示行、列、层。距离记录使用三维数组dist[z][x][y]记录从起点到该状态的最短步数初始化为−1-1−1表示未访问。BFS\texttt{BFS}BFS队列将起点状态加入队列距离设为000。状态扩展对于队列中的每个状态尝试所有可能的移动四方向移动在同一层内向上、下、左、右移动若目标位置不是墙壁且未访问则更新距离并入队。电梯移动若当前位置是电梯-则检查相邻楼层上一层和下一层的同一位置是否也是电梯。若是则移动到对应楼层更新距离并入队。终止条件当访问到终点状态时立即返回其距离若队列空仍未访问到终点返回−1-1−1。时间复杂度每个状态最多入队一次每次扩展最多666个方向444个平面方向 222个电梯方向。总复杂度O(l×w×h)O(l \times w \times h)O(l×w×h)在1003106100^3 10^61003106范围内可接受。空间复杂度需要存储迷宫和距离数组均为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//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN105;// 最大维度structPoint{intx,y,z;// x:行, y:列, z:层Point(intx,inty,intz):x(x),y(y),z(z){}};// 方向数组dx 表示行变化dy 表示列变化intdx[]{1,-1,0,0,0,0},dy[]{0,0,1,-1,0,0};chargrid[MAXN][MAXN][MAXN];// 存储迷宫[层][行][列]intdist[MAXN][MAXN][MAXN];// 存储距离[层][行][列]intbfs(Point start,Point end,intl,intw,inth){// 初始化距离为 -1未访问memset(dist,-1,sizeofdist);queuePointq;dist[start.z][start.x][start.y]0;q.push(start);while(!q.empty()){Point pq.front();q.pop();// 到达终点返回最短步数if(p.xend.xp.yend.yp.zend.z)returndist[p.z][p.x][p.y];// 四方向移动同一层内for(inti0;i4;i){intnxp.xdx[i],nyp.ydy[i],nzp.z;if(nx0nxlny0nywnz0nzh){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(intdz:{1,-1}){// 上楼和下楼intnzp.zdz;if(nz0nzhgrid[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;// 无法到达终点}intmain(){intl,w,h;while(cinlwh){if(l0w0h0)break;Pointstart(0,0,0),end(0,0,0);// 读取 h 层每层 l 行每行 w 个字符for(intk0;kh;k){for(inti0;il;i){// 每层有 l 行string line;cinline;for(intj0;jw;j){// 每行有 w 列grid[k][i][j]line[j];if(line[j]S)startPoint(i,j,k);// 记录起点if(line[j]E)endPoint(i,j,k);// 记录终点}}}intrbfs(start,end,l,w,h);coutrendl;}return0;}代码要点解析数组维度使用grid[z][x][y]和dist[z][x][y]表示第zzz层第xxx行第yyy列的状态。注意坐标顺序层、行、列。BFS\texttt{BFS}BFS初始化使用memset(dist, -1, sizeof dist)快速初始化距离数组。电梯移动条件仅当grid[p.z][p.x][p.y] -且相邻楼层的相同位置也是-时才允许上下楼。边界检查移动时检查新位置是否在迷宫范围内。输入处理由于题目保证每行长度正确直接按行读取即可。样例分析样例输入 14 4 3 S..- #.## ..#- -#E. ...- .### .#.- -#.. .#.- .#.# .#.- ...#输出131313解释如题目图示需要131313步从起点到达终点中间可能多次换层。样例输入 22 4 2 .-.. .... S--E ####输出333解释起点和终点在同一层直接向右移动333步即可到达无需使用电梯。总结本题是三维BFS\texttt{BFS}BFS的经典应用主要考察对状态空间的理解和BFS\texttt{BFS}BFS的实现能力。关键点在于正确处理电梯移动规则必须两端都是电梯以及使用BFS\texttt{BFS}BFS保证首次到达即为最短路径。代码实现时需要注意数组维度的顺序和边界条件的检查。
