eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

"Минимизация поворотов"

"Минимизация поворотов"

Рассмотрим карту лабиринта в виде прямоугольника, заполненную нулями и единицами, в которой "\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}" (без кавычек).
Лимит времени 2 секунды
Лимит использования памяти 64 MiB
Входные данные #1
5 6
110111
000001
101101
100001
111111
4 5
Выходные данные #1
2
Автор Илья Порублёв
Источник ACM-ICPC Ukraine 2013, 2nd Stage Ukraine, September 10-12, 2013