Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Вам дана карта, на которой приведён вид сверху на этажи многоэтажного лабиринта. Символом '.' обозначены свободные (проходимые) комнаты, символом '#' — непроходимые.
Вы находитесь в комнате, помеченной символом '1', и хотите попасть в комнату, помеченную символом '2'. Из любой комнаты вы можете перемещаться в соседние по стороне свободные комнаты, а также в свободные комнаты, расположенные выше и ниже этажом.
Определите минимальное количество шагов, требуемое для попадания из комнаты '1' в комнату '2'. Гарантируется, что это возможно сделать.
Входные данные
Первая строка содержит целые числа H, N и M (2 <= H, N, M <= 50) — высоту, длину и ширину лабиринта соответственно.
Далее следуют H блоков, описывающих этажи лабиринта. Каждый блок содержит N строк по M символов. Блоки разделяются одной пустой строкой.
Выходные данные
Выведите единственное целое число — ответ на задачу.
Примеры
| Входные данные | Выходные данные |
2 2 3
1#.
.#2
#..
..#
| 7 |
3 2 4
#..#
#.#.
1#.#
..##
##..
..#2
| 9 |
Для отправки решений необходимо выполнить вход.
|