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:

start

f

f

f

f

r

f

r

f

f

f

f

f

f

f

r

r

r

X

“f” means forward, “r” means a right-turn, and “?” means nowhere to go.
Note that the green square is crossed twice by Weighd.

start

f

f

f

f

r

f

?

f

f

f

f

r/f

f

X

f

?

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.

Input Specification

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).

Output Specification

The output consists of one line for each maze. It will be in one of the following two formats:

1. An integer that represents the number of steps to be taken by Weighd inside the maze to reach its destination.
2. The string “NOOO!” if no path can be found.

Sample Input

1. 6 13
2. 13 4
3. 0000001111000
4. 0111101111000
5. 0000000000000
6. 0000001111110
7. 0000001111110
8. 0000000000000
9. 6 13
10. 13 4
11. 0000001111000
12. 1111101111000
13. 0000000000000
14. 0001101111110
15. 0001101111110
16. 0001100000000
17. 0 0

download as text file

Output for Sample Input

1. 19
2. NOOO!

download as text file