May the Right-Force Be with You
In a sensational scene in the 8th installment of the Voldemort book series, the robot Weighd was attacked, and its rotating top and wings were severely damaged. Weighd cannot rotate its famous top and can only fly forward or make a right-turn. However, the brave Weighd must still navigate a magically created series of mazes to deliver its precious message to Ttoper.
Weighd enters each maze at the top-left square of the maze, takes one unit of time to travel between adjacent squares in the magic maze (forward or right), and cannot stay in one square to rotate itself, and thus change direction, for fear of evil jinx. Your task is to write a program to calculate the smallest number of squares that Weighd must travel to reach a certain square in each maze. Do you worry about how? Weighd will feel its correct way through the force. Examples are:
Note that the green square is crossed twice by Weighd.
Weighd can reach the location marked “X” of the top maze in 19 steps, but it cannot reach the marked location in the bottom maze at all.
The input consists of multiple mazes. Each maze description starts with two integers, on a separate line, that represent its dimensions. The first integer N (1 ≤ N ≤ 1000) represents the number of rows, and the second M (1 ≤ M ≤ 1000) represents the number of columns. The last maze is followed by a line containing two zeros that indicate the end of the input data and should not be processed as a valid situation.
The second line contains two integers, C (1 ≤ C ≤ N) and R (1 ≤ R ≤ M) that represent the column number and the row number of the square where Weighd must reach in the maze. Consecutive integers are separated by a blank space.
Each of the following N lines contains a sequence of 0s and 1s. The sequence is M characters long. The sequence does not contain blank spaces. A value one (1) represents a wall in the maze (that is, a square into which Weighd cannot fly).
The output consists of one line for each maze. It will be in one of the following two formats:
Output for Sample Input
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|