eolymp
bolt
Try our new interface for solving problems
Məsələlər

Лабиринт

Лабиринт

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Открыв глаза, Принц Персии обнаружил, что находится на верхнем уровне подземного лабиринта Джаффара. Лабиринт состоит из h уровней, расположенных строго друг под другом. Каждый уровень представляет собой прямоугольную площадку, разбитую на m * n участков. На некоторых участках стоят колонны, поддерживающие потолок, на такие участки Принц заходить не может.

Принц может перемещаться с одного участка на другой участок того же уровня, если у этих участков есть общая сторона, и ни один из этих участков не содержит колонну. Это перемещение занимает у Принца 5 секунд.

Полы в лабиринте Джаффара чрезвычайно тонкие, и Принцу не составляет труда сильным ударом ноги проломить пол под собой, если только на соответствующем участке нижнего уровня не находится колонна. Когда пол проламывается, Принц проваливается на один уровень вниз, при этом не перемещаясь в горизонтальной плоскости. Это действие также занимает у Принца 5 секунд. Конечно, если Принц уже находится на самом нижнем уровне, то пол под ним не проломится.

На одном из участков нижнего уровня Принца ждет Принцесса, отказавшаяся выйти замуж за злого Джаффара. Помогите Принцу найти Принцессу, потратив на это как можно меньше времени.

Giriş verilənləri

В первой строке содержатся натуральные числа h, m и n (2h, m, n50) - высота и горизонтальные размеры лабиринта. Далее приведены h блоков, описывающих уровни лабиринта в порядке от верхнего к нижнему.

Каждый блок содержит m строк по n символов в каждой: "." (точка) обозначает свободный участок, "o" (строчная латинская буква "o") обозначает участок с колонной, "1" обозначает свободный участок, в котором оказался Принц в начале своего путешествия, "2" обозначает свободный участок, на котором томится Принцесса.

Символы "1" и "2" встречаются ровно по одному разу: символ "1" в описании самого верхнего уровня, а символ "2" в описании самого нижнего.

Соседние блоки разделены одной пустой строкой.

Çıxış verilənləri

Выведите минимальное время в секундах, необходимое Принцу, чтобы найти Принцессу. Поскольку Добро всегда побеждает Зло, гарантируется, что Принц может это сделать.

Nümunə

Giriş verilənləri #1
3 3 3
1..
oo.
...

ooo
..o
.oo

ooo
o..
o.2
Çıxış verilənləri #1
60
Mənbə 2006, XIV Командный чемпионат школьников Санкт-Петербурга по программированию, 6 ноября, Задача G