#238. Dungeon Master

Dungeon Master

题目描述

你被困在一个三维的空间中,现在要寻找最短路径逃生!

空间由立方体单位构成

你每次向上下前后左右移动一个单位需要一分钟

你不能对角线移动并且四周封闭

是否存在逃出生天的可能性?如果存在,则需要多少时间?

输入

输入第一行是一个数表示空间的数量。

每个空间的描述的第一行为L,R和C(皆不超过30)。

L表示空间的高度。

R和C分别表示每层空间的行与列的大小。

随后L层地牢,每层R行,每行C个字符。

每个字符表示空间的一个单元。'#'表示不可通过单元,'.'表示空白单元。你的起始位置在'S',出口为'E'。

每层空间后都有一个空行。L,R和C均为0时输入结束。

输出

每个空间对应一行输出。

如果可以逃生,则输出如下

Escaped in x minute(s).

x为最短脱离时间。

如果无法逃生,则输出如下

Trapped!

输入样例

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

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

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

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

0 0 0

输出样例

Escaped in 11 minute(s).
Trapped!

提示

对于题目给出数据的含义就是输入l,r,c,分别代表迷宫有l层,每层长宽分别是c,r。

对于数据一可以这样移动:

(1,1,1) -> (1,1,2) -> (1,1,3) -> (1,1,4) -> (1,1,5) -> (1,2,5) ->
(1,3,5) -> (1,3,4) -> (1,4,4) -> (2,4,4) -> (2,4,5) -> (3,4,5)

共11步就可以到达终点

对于数据二明显不能到达,则输出Trapped!