#AG0206. 地牢大师

地牢大师

题目描述

你被困在3D地牢中,需要找到最快的出路!地牢是由立方网格组成的,有的区域是道路,有的区域是石墙。向北、向南、向东、向西、向上或向下移动一个单元需要一分钟。你不能对角移动,迷宫四周都是坚硬的岩石。

有可能逃跑吗?如果是,需要多长时间?

输入格式

输入由许多地下城组成。每组数据都以一行开头,其中包含三个整数 L,R,C(1L,R,C100)L,R,C(1≤L,R,C≤100)

LL是构成地牢的层数,RRCC是构成每一层平面图的行数和列数。

然后是LLRR行块,每个RR行块包含CC个字符。每个角色描述了地牢的一个单元。石墙的单元格用#表示,空地单元格用.表示。您的起始位置用S表示,出口用字母E表示。每层楼后面都有一个空行。L,R,CL,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×CL×R×C之和不超过10610^6