题目描述

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

空间由立方体单位构成，你每次向上下前后左右移动一个单位需要一分钟，你不能对角线移动并且四周封闭。是否存在逃出生天的可能性？如果存在，则需要多少时间？

输入格式

输入包含多组测试数据。

每组数据的第一行为 $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!

第一组数据可以这样移动：$(1,1,1)\to (1,1,2)\to (1,1,3)\to (1,1,4)\to (1,1,5)\to (1,2,5)\to (1,3,5)\to (1,3,4)\to (1,4,4)\to (2,4,4)\to (2,4,5)\to (3,4,5)$。共 $11$ 步就可以到达终点。