|
Жук
(Время: 2 сек. Память: 16 Мб Сложность: 30%)
Петя нашел в Интернете по адресу http://buglab.ru игру-головоломку "Жук", в которой от участников требуется построить для жука лабиринт таким образом, чтобы жук как можно дольше искал выход.
Жук всегда начинает свое движение с левого верхнего угла, а выход всегда находится в правом нижнем. Жук движется не оптимально, а следующим образом: он идет туда, где еще не был, либо был там реже. Т.е. проходя каждую клетку лабиринта, жук запоминает: сколько раз он был в этой клетке и при обдумывании направления своего движения в какой то конкретный момент он смотрит: сколько раз он был в клетке снизу, сколько справа, сколько слева и сколько сверху и движется туда, где он был меньше раз. Если таких направлений несколько и одно из них совпадает с текущим направлением движения, то он не меняет направления, иначе он движется согласно следующим приоритетам: вниз, направо, вверх, налево. Т.е. если минимальное число посещений сразу справа и слева (а двигался он при этом вверх или вниз), то жук идет направо, т.к. у "направо" приоритет выше. Следует заметить, что двигаясь по данному алгоритму жук всегда достигнет выхода в том случае, когда выход существует.
Изучив алгоритм движения жука Петя хочет написать программу, которая по заданному лабиринту определит количество перемещений жука прежде, чем он достигнет выхода. Помогите Пете с реализацией данной программы!
Конструктор лабиринта
Входные данные
Входной файл INPUT.TXT в первой строке содержит разделенные пробелом целые числа N и M - количество строк и столбцов в лабиринте (4 ≤ N, M ≤ 100). Далее следует N строк, содержащих данные лабиринта построчно. Каждая строка содержит M символов - клетки лабиринта текущей строки, где символ "@" обозначает присутствие стены, а символ пробела - пустое пространство. Гарантируется, что граница лабиринта окружена стеной. Предполагается, что жук начинает свое движение из координаты (2, 2) и заканчивает в координате (M-1, N-1), подразумевается, что в этих координатах нет стен. Гарантируется, что если выход из лабиринта существует, то жук сможет выйти из него, сделав не более 107 шагов.
Выходные данные
В выходной файл OUTPUT.TXT выведите количество движений жука, если спасительный маршрут для жука существует, и -1 в противном случае.
Примеры
¹ | INPUT.TXT | OUTPUT.TXT |
1 | 6 6
@@@@@@
@ @
@ @
@ @ @@
@ @ @
@@@@@@
| 20 |
2 | 8 30
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ @ @ @@@@ @ @ @@@@ @@ @
@ @ @@ @ @ @ @ @ @ @
@ @ @ @ @@ @@ @@ @@
@ @ @ @@
@ @ @@ @ @ @@@ @ @ @ @
@ @ @ @ @ @ @@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
| 630 |
3 | 4 4
@@@@
@ @@
@@ @
@@@@
| -1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |