eolymp
bolt
Try our new interface for solving problems
Məsələlər

"Turns minimization"

"Turns minimization"

Consider a map of maze in the form of rectangular table filled with zeroes and ones, where "\textbf{0}" means a free cell and "\textbf{1}" means a wall. Robot initially is in the cell with coordinates \textbf{(i_0, j_0)}. It should be moved outside the maze (via any free cell in any outer side). Robot can move to any free of four neighboring cells (left, right, up, down). Robot’s significant feature is that it can pass many free cells in the same direction very quickly, but each turn (direction changing) requires a lot of time. Your task is to write a program finding the way to move outside the maze with minimal number of turns. \InputFile The \textbf{1^st} line of input contains two integers \textbf{N}, \textbf{M} (\textbf{5} ≤ \textbf{N},_\{ \}\textbf{M} ≤ \textbf{640}) which are the size of the maze. Each of following \textbf{N }lines contains exactly \textbf{M} ones and/or zeroes (without any delimiters), denoting walls and free cells. The next and the last line contains two integers \textbf{i_0}, \textbf{j_0} (\textbf{2} ≤ \textbf{i}_\{0 \}≤ \textbf{N--1}, \textbf{2} ≤ \textbf{j}_\{0 \}≤ \textbf{M--1}) which are initial coordinates. It’s guaranteed that initial coordinates correspond to free cell, but it’s unknown whether any way out exists. \OutputFile Output exactly one integer --- the minimal number of same-directed fragments of way outside. If no way out exists, program should output "\textbf{--1}" (without quotes).
Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
5 6
110111
000001
101101
100001
111111
4 5
Çıxış verilənləri #1
2
Müəllif Ilya Porublev
Mənbə ACM-ICPC Ukraine 2013, 2nd Stage Ukraine, September 10-12, 2013