Задачи
"Минимизация поворотов"
"Минимизация поворотов"
Рассмотрим карту лабиринта в виде прямоугольника, заполненную нулями и единицами, в которой "\textbf{0}" обозначает свободное место, а "\textbf{1}" - стенку.
Изначально робот находится в ячейке с координатами \textbf{(i_0, j_0)}. Ему необходимо выбраться из лабиринта (через свободные ячейки в любую сторону). Робот может двигаться в любую из четырех соседних свободных ячеек (налево, направо, вверх и вниз). Отличительная черта робота состоит в том, что он может быстро преодолевать много свободных ячеек в одном направлении, однако каждый поворот (изменение направления) требует много времени.
Напишите программу, которая поможет роботу выбраться из лабиринта, совершив при этом наименьшее количество поворотов.
\InputFile
Первая строка содержит два целых числа \textbf{N}, \textbf{M} (\textbf{5} ≤ \textbf{N},_\{ \}\textbf{M} ≤ \textbf{640}), задающие размер лабиринта. Каждая из следующих \textbf{N }строк содержит в точности \textbf{M} единиц и/или нулей (без разделителей), обозначающих стены и свободные ячейки. Следующая и последняя строка содержит два целых числа \textbf{i_0}, \textbf{j_0} (\textbf{2} ≤ \textbf{i}_\{0 \}≤ \textbf{N--1}, \textbf{2} ≤ \textbf{j}_\{0 \}≤ \textbf{M--1}) - начальные координаты робота. Гарантируется, что начальные координаты принадлежат пустой ячейке, однако не известно, существует ли выход.
\OutputFile
Вывести одно число - наименьшее количество однонаправленных участков на пути наружу. Если выхода из лабиринта нет, то вывести "\textbf{--1}" (без кавычек).
Входные данные #1
5 6 110111 000001 101101 100001 111111 4 5
Выходные данные #1
2