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 64 MiB

Игрушечный лабиринт представляет собой прозрачную плоскую прямоугольную коробочку, внутри которой есть препятствия и перемещается шарик. Коробку можно наклонять вправо, влево, к себе или от себя, после каждого наклона шарик перемещается в заданном направлении до ближайшего препятствия или до стенки лабиринта, после чего останавливается. Целью игры является загнать шарик в одно из специальных отверстий-выходов. Шарик проваливается в отверстие, если оно встречается на его пути (шарик не обязан останавливаться в отверстии).

Первоначально шарик находится в левом верхнем углу лабиринта. Гарантируется, что решение существует и левый верхний угол не занят препятствием или отверстием.

Giriş verilənləri

В первой строке входного файла записаны числа N и M - размеры лабиринта (целые положительные числа, не превышающие 100). Затем идёт N строк по M чисел в каждой - описание лабиринта. Число 0 в описании обозначает свободное место, число 1 - препятствие, число 2 - отверстие.

Например, лабиринту, изображённому на рисунке, будет соответствовать такое описание:

Çıxış verilənləri

Выведите единственное число - минимальное количество наклонов, которые необходимо сделать, чтобы шарик покинул лабиринт через одно из отверстий.

Nümunə

Giriş verilənləri #1
4 5
0 0 0 0 1
0 1 1 0 2
0 2 1 0 0
0 0 1 0 0
Çıxış verilənləri #1
3