Turns minimization#6085
Consider a maze represented as a rectangular grid consisting of zeros and ones, where 0 denotes a free cell and 1 denotes a wall.
A robot initially stands at the cell with coordinates (i_0, j_0). The robot's task is to exit the maze (by reaching any free cell on any outer edge). The robot can move to any free cell adjacent vertically or horizontally (not diagonally). Its unique feature is that it can traverse any number of consecutive free cells in the same direction quickly, but changing direction (making a turn) takes a significant amount of time.
Your task is to determine the minimum number of turns required for the robot to exit the maze. If exiting is impossible, output –1.
The first line contains two integers , (5 \leq N,\ M \leq 640) — the height and width of the maze. Each of the next lines contains exactly characters (either 0 or 1) without separators, representing the maze: is a free cell and is a wall. The final line contains two integers i_0, j_0 (2 \leq i_0 \leq N-1, 2 \leq j_0 \leq M-1) — the initial coordinates of the robot. It is guaranteed that these coordinates correspond to a free cell, but there might not exist a path to the boundary.
Print a single integer — the minimum number of direction changes (turns) required for the robot to reach any cell on the boundary of the maze. If there is no possible way out, print –1 (without quotation marks).
Example 1