#6555. 逃离地牢 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

贝茜被困在了一个三维立体的地牢里,这个地牢是一个立方体,由通道和岩石组成。

贝茜只能往东、南、西、北、上、下六个方向走,且每走一步要花费1个单位的时间。

现在将地牢的详细布局给你?你能逃出地牢么?如果能的话,最少要花多少时间呢?

输入格式

第一行包括三个数L R C,分别表示地牢的长宽高。(长宽高不会超过30)

接下来输入L个R*C的矩阵,两个矩阵之间用一个空行隔开,描述地牢的详细情况。

其中‘S’表示贝茜的起点,‘E’表示终点,‘.’表示该位置是通道,可以通行,‘#’表示该位置为岩石,不可以通行。

起点终点各只有一个

输出格式

如果可以达到终点,输入:” Escaped in x minute(s).”,其中x表示最短的时间;

如果无法到达终点,输出:"Trapped!"。

样例

样例输入

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

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

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

样例输出

Escaped in 11 minute(s).