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