e-olymp
Задачі

Підземелля

Підземелля

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

Чи можна вибратись з лабіринту? Якщо так, то який час це займе?

Вхідні дані

Вхідні дані складаються з ряду підземель. Кожен опис підземелля починається з рядка, що містить три цілих числа L, R і С (всі числа не більші 30).

L - це кількість рівнів у підземеллі.

R і С - кількість рядків і стовбців, які описують план кожного рівня.

Далі йде L блоків по R рядків, кожен з яких по С символів. Кожне число описує одну комірку підземелля. Заборонені для переміщення куби підземелля позначені символом '#', а пусті клітини позначені '.'. Ваша стартова позиція позначається буквою 'S', а вихід буквою 'Е'. Всі описи підземель відокремлені пустим рядком. Опис вхідних даних закінчується трьома нулями.

Вихідні дані

Для кожного лабіринту потрібно вивести один рядок. Якщо є можливість дістатись до виходу, вивести рядок виду

Escaped in X minute(s).

де X - найменший час, потрібний для досягнення виходу.

Якщо досягнути виходу неможливо, вивести рядок

Trapped!

Ліміт часу 1 секунда
Ліміт використання пам'яті 122.17 MiB
Вхідні дані #1
3 4 5
S....
.###.
.##..
###.#

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

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

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

0 0 0
Вихідні дані #1
Escaped in 11 minute(s).
Trapped!