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).
Giriş verilənləri #1
5 6 110111 000001 101101 100001 111111 4 5
Çıxış verilənləri #1
2