UVA-532 - Dungeon Master

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 本題選為「20170926 / 20110525 大學程式能力檢定 CPE」題目。
• 相同題目：ZOJ-c124

題意概要

題目給定 3D 迷宮的大小 (長、寬、高)，並將每筆測資的迷宮起點與終點分別以 S 與 E 表示，而迷宮的牆壁以 # 表示，迷宮的道路以 . 表示。此外，在這個迷宮中，能夠走的方向有「東、西、南、北、上、下」。試求：從 S 走到 E 的最短路徑。如果無法走到出口，則要輸出 Trapped!。

• 分析：本題為「廣度優先搜尋 (BFS)」的應用。在使用 BFS 時，可以使用「佇列 (queue)」模擬 (記得：#include <queue>)，唯獨要注意，當一個位置進入佇列時，就要將該位置封閉，避免該位置再次進入佇列發生 TLE 的錯誤。

Input

The input file consists of a number of dungeons. Each dungeon description starts with a line containing three integers $L$, $R$ and $C$ (all limited to $30$ in size).

• $L$ is the number of levels making up the dungeon.
• $R$ and $C$ are the number of rows and columns making up the plan of each level. Then there will follow $L$ blocks of $R$ lines each containing $C$ characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a # and empty cells are represented by a .. Your starting position is indicated by S and the exit by the letter E. There’s a single blank line after each level. Input is terminated by three zeroes for $L$, $R$ and $C$.

Output

Each maze generates one line of output. If it is possible to reach the exit, print a line of the form Escaped in x minute(s). where x is replaced by the shortest time it takes to escape. If it is not possible to escape, print the line Trapped!

Sample Input

3 4 5
S....
.###.
.##..
###.#

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

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

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

0 0 0

Sample Output

Escaped in 11 minute(s).
Trapped!