|
Лабиринт
(Время: 1 сек. Память: 16 Мб Сложность: 55%)
Открыв глаза, Принц Персии обнаружил, что находится на верхнем уровне подземного лабиринта Джаффара. Лабиринт состоит из h уровней, расположенных строго друг под другом. Каждый уровень представляет собой прямоугольную площадку, разбитую на m х n участков. На некоторых участках стоят колонны, поддерживающие потолок, на такие участки Принц заходить не может.
Принц может перемещаться с одного участка на другой соседний свободный участок того же уровня, так же он может проломить пол под собой и оказаться уровнем ниже (на самом нижнем уровне пол проломить нельзя). Любое перемещение занимает у Принца 5 секунд.
На одном из участков нижнего уровня Принца ждет Принцесса. Помогите Принцу найти Принцессу, потратив на это как можно меньше времени.
Входные данные
В первой строке входного файла INPUT.TXT содержатся натуральные числа h, m и n — высота и горизонтальные размеры лабиринта (2 ≤ h, m, n ≤ 50). Далее во входном файле приведены h блоков, описывающих уровни лабиринта в порядке от верхнего к нижнему. Каждый блок содержит m строк, по n символов в каждой: «.» обозначает свободный участок, «о» обозначает участок с колонной, «1» обозначает свободный участок, в котором оказался Принц в начале своего путешествия, «2» обозначает свободный участок, на котором томится Принцесса. Символы «1» и «2» встречаются во входном файле ровно по одному разу: символ «1» — в описании самого верхнего уровня, а символ «2» — в описании самого нижнего. Соседние блоки разделены одной пустой строкой.
Выходные данные
В выходной файл OUTPUT.TXT выведите минимальное время в секундах, необходимое Принцу, чтобы найти Принцессу. Поскольку добро всегда побеждает Зло, гарантируется, что Принц может это сделать.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 3 3
1..
oo.
...
ooo
..o
.oo
ooo
o..
o.2
| 60 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
