题目描述

你被困在一个3D地牢中，需要找到最快的逃脱路径！地牢由单位立方体组成，这些立方体可能被岩石填充或为空。每次移动可以朝北、南、东、西、上或下移动一个单位，耗时1分钟。不能斜向移动，且迷宫四周都是坚硬的岩石。

能否逃脱？ 如果可以，最少需要多少时间？

输入格式

输入包含多个地牢的描述。每个地牢描述的第一行是三个整数 $L$、$R$ 和 $C$（均不超过30）。

• $L$ 表示地牢的层数。
• $R$ 和 $C$ 表示每一层的行数和列数。

接下来是 $L$ 个区块，每个区块包含 $R$ 行，每行 $C$ 个字符。字符含义如下：

• # 表示岩石（不可通行）。
• . 表示空地（可通行）。
• S 表示起点。
• E 表示出口。

每个层描述后有一个空行。输入以 $0\ 0\ 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!  

来源

Ulm Local 1997