eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Подземелье

Подземелье

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Вы попали в 3D подземный лабиринт и необходимо найти быстрый выход! Карта подземелья составлена из единичных кубических комнат, по которым можно или нельзя передвигаться. Нужно всего одну минуту, чтобы переместиться она одну единицу на север, юг, восток, запад, вверх или вниз. Вы не можете двигаться по диагонали, и лабиринт окружен твердой скальной породой со всех сторон.

Можно ли выбраться из лабиринта? Если да, то какое времени это займет?

Входные данные

Состоит из ряда подземелий. Каждое описание подземелья начинается со строки, содержащей три целых числа: количество уровней в подземелье l, а также r и c - количество строк и столбцов, описывающих план каждого уровня (все числа не больше 30).

Далее следует l блоков по r строк, каждая по c символов. Каждое число описывает одну ячейку подземелья. Запрещенные для перемещения кубы подземелья обозначены символом '#', а пустые клетки обозначены '.'. Ваша стартовая позиция обозначается буквой 'S', а выход буквой 'Е'. Все описания подземелий отделены пустой строкой. Описание входных данных заканчивается тремя нулями.

Выходные данные

Для каждого лабиринта необходимо вывести одну строку. Если есть возможность добраться до выхода, вывести строку вида Escaped in X minute(s).

где X - наименьшее время, необходимое для достижения выхода.

Если достичь выход невозможно, вывести строку

Trapped!

Пример

Входные данные #1
3 4 5
S....
.###.
.##..
###.#

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

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

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

0 0 0
Выходные данные #1
Escaped in 11 minute(s).
Trapped!