|
Игрушечный лабиринт
(Время: 1 сек. Память: 16 Мб Сложность: 51%)
Игрушечный лабиринт представляет собой прозрачную плоскую прямоугольную коробку, внутри которой есть препятствия и перемещается шарик. Лабиринт можно наклонять влево, вправо, к себе или от себя, после каждого наклона шарик перемещается в заданном направлении до ближайшего препятствия или до стенки лабиринта, после чего останавливается. Целью игры является загнать шарик в одно из специальных отверстий – выходов. Шарик проваливается в отверстие, если оно встречается на его пути (шарик не обязан останавливаться в отверстии).
Первоначально шарик находится в левом верхнем углу лабиринта. Гарантируется, что решение существует, и левый верхний угол не занят препятствием или отверстием.
Входные данные
В первой строке входного файла INPUT.TXT записаны целые числа N и M – размеры лабиринта (1 ≤ N, M ≤ 100). Затем идет N строк по M чисел в каждой – описание лабиринта. Число 0 в описании означает свободное место, число 1 – препятствие, число 2 – отверстие.
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число – минимальное количество наклонов, которые необходимо сделать, чтобы шарик покинул лабиринт через одно из отверстий.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 5
0 0 0 0 1
0 1 1 0 2
0 2 1 0 0
0 0 1 0 0 | 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
