题目描述

题目要求在一个三维迷宫中，从起点S出发，找到通往终点E的最短路径。迷宫由若干层组成，每层有若干行和列。每个单元可以是空地（.）、岩石（#）、起点（S）或终点（E）。每次移动可以向六个方向（北、南、东、西、上、下）移动一格，耗时111分钟。输出最短时间，若无法到达则输出Trapped!。

输入格式

输入包含多个迷宫。每个迷宫的第一行包含三个整数LLL、RRR、CCC（1≤L,R,C≤301 \le L, R, C \le 301≤L,R,C≤30），分别表示层数、行数和列数。接下来LLL个块，每个块包含RRR行，每行CCC个字符。每个块之后有一个空行。输入以0 0 0结束。

输出格式

对于每个迷宫，输出一行：若能到达，输出Escaped in x minute(s).；否则输出Trapped!。

样例

输入

3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0

输出

Escaped in 11 minute(s). Trapped!

题目分析

本题的核心是在三维网格中进行广度优先搜索（BFS\texttt{BFS}BFS）寻找最短路径。

BFS\texttt{BFS}BFS实现

• 使用队列存储状态(i,j,k,dist)(i, j, k, dist)(i,j,k,dist)，其中(i,j,k)(i, j, k)(i,j,k)为坐标，distdistdist为距离。
• 从起点开始，向666个方向扩展。
• 遇到障碍（#）或已访问过则跳过。
• 遇到终点E则输出当前距离。
• 若队列为空仍未找到终点，则输出Trapped!。

复杂度分析

网格大小L×R×C≤27,000L \times R \times C \le 27,000L×R×C≤27,000，BFS\texttt{BFS}BFS时间复杂度O(L×R×C)O(L \times R \times C)O(L×R×C)。

代码实现

// Dungeon Master// UVa ID: 532// Verdict: Accepted// Submission Date: 2016-08-07// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structstate{inti,j,k,minutes;};intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);chargrid[32][32][32],visited[32][32][32];intL,R,C;while(cin>>L>>R>>C,L&&R&&C){intstarti,startj,startk,endi,endj,endk;for(inti=0;i<L;i++)for(intj=0;j<R;j++)for(intk=0;k<C;k++){cin>>grid[i][j][k];if(grid[i][j][k]=='S')starti=i,startj=j,startk=k;if(grid[i][j][k]=='E')endi=i,endj=j,endk=k;}memset(visited,0,sizeof(visited));queue<state>unvisited;unvisited.push((state){starti,startj,startk,0});boolescaped=false;while(!unvisited.empty()){state current=unvisited.front();unvisited.pop();if(current.i<0||current.i>=L||current.j<0||current.j>=R||current.k<0||current.k>=C||grid[current.i][current.j][current.k]=='#'||visited[current.i][current.j][current.k])continue;visited[current.i][current.j][current.k]=1;if(current.i==endi&&current.j==endj&&current.k==endk){cout<<"Escaped in "<<current.minutes<<" minute(s).\n";escaped=true;break;}unvisited.push((state){current.i-1,current.j,current.k,current.minutes+1});unvisited.push((state){current.i+1,current.j,current.k,current.minutes+1});unvisited.push((state){current.i,current.j-1,current.k,current.minutes+1});unvisited.push((state){current.i,current.j+1,current.k,current.minutes+1});unvisited.push((state){current.i,current.j,current.k-1,current.minutes+1});unvisited.push((state){current.i,current.j,current.k+1,current.minutes+1});}if(!escaped)cout<<"Trapped!\n";}return0;}