Canadian Computing Competition: 2002 Stage 2, Day 1, Problem 3

You have all played Blind Man's Bluff before, in an earlier Stage of life. In this sequel, you have even less information to work with, and you need to provide even more detailed responses. Recall that the "game" of Blind Man's Bluff is as follows: the player is placed in a known ~n \times m~ playing area (with obstacles of size ~1~ square unit placed at various points in the playing area) pointing in one of the ~4~ compass directions (North, East, South, West). After moving in forward (F), turning right (R), or turning left (L), you were to determine your original starting position and the compass direction you were pointing in (either N=North, S=South, E=East, W=West).

We augment this game slightly now. Instead of simply determining your starting position and your direction, you are to determine the game board layout. That is, you are really playing this game blind. To help you in this endeavour, you are given the dimensions of the board, your starting position (in coordinates) and your starting orientation (either N=North, S=South, E=East, W=West).

However, you have access to a query engine that will tell you whether the move you wish to perform is possible. It is always possible to turn right or left, though it may be impossible to move forward if there is an obstacle or wall (i.e., the boundary of the board) in front of you. This interactor can be given the following instructions:

• R: Turn right ~90~ degrees in the playing area.

• L: Turn left ~90~ degrees in the playing area.

• F: Move forward and output 1 if there is no obstacle or wall in the position immediately (~1~ unit) in front of you. Outputs 0 and does not change position or compass orientation if there is a wall or an obstacle ~1~ unit in front of you.

• A: Tell the interactor you have an answer and output it to be graded.

You may assume that it is possible to map out the entire game area. For example, you will NOT have the following type of playing area in the ~5 \times 5~ case

....X
.XX..
.X.X.
..XX.
.....

since if you were placed at position ~(3,3)~, you would be unable to determine the obstacles at positions ~(1,5)~, ~(2,2)~ and ~(4,4)~. In other words, there are no unreachable spaces in the playing area.

Interaction

The first line will contain ~n~ ~(1 \le n \le 75)~, the number of rows.

The second line will contain ~m~ ~(1 \le m \le 75)~, the number of columns.

The third line will contain your starting row ~r~ ~(1 \le r \le n)~.

The fourth line will contain your starting column position ~c~ ~(1 \le c \le m)~.

The fifth line will contain the starting orientation: that is, one of the characters, N, S, E, W.

To move forward, you can output F, and the interactor will return either a 1 to indicate that it was successful or a 0 to indicate it was not.

To move left, you can output L; to move right, you can output R.

Once you have constructed the playing area, output A followed by ~n~ lines with ~m~ characters, the board.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Sample Interaction

>>> denotes your output. Do not print this out.

The playing area is:

..
X.

2
2
1
1
N
>>> F
0
>>> R
>>> F
1
>>> F
0
>>> R
>>> F
1
>>> R
>>> F
0
>>> A
>>> ..
>>> X.