Day 1 Question 3: Return to Blind Man’s Bluff

Your solution: N:\bluff\bluff.{pas, c, cpp}
Input file: bluff.in
Output file: bluff.out

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 x 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 endeavor, you are given the dimensions of the board, your starting position (in co-ordinates) 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 query engine is contained within module called query that has the following functions:

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 5x5 case

. . . . X
. X X . .
. X . X .
. . X X .
. . . . .

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.

Testing Your Program

The query module reads the description of a test case from the file query.in. This file contains the values n, m, r, and c, each on a separate line, followed by the game board in the format described above. You can modify this file by hand in order to test your program. Of course, your program must not read directly from this file.

The query module outputs a file named query.log which describes the calls that your program made to the module.

Instructions for Pascal Programmers

To access the library, your program must contain the statement

uses query;

For your information, here are the function and procedure declarations:

procedure Right;
procedure Left;
function Forward:integer;

Instructions for C/C++ Programmers

Use the instruction #include "query.h" in your source code. Use the "Open Project..." command to create a new project. Add your source file and the module query.o to your project.

Input

Input will be on 5 separate lines. The first line contains n (number of rows). The second line contains m (number of columns). Following that, you are given your starting row r (1 <= r <= n) on one line, followed by your starting column position c (1 <= c <= m) on the next line. The fifth line will contain the starting orientation: that is, one of the characters, N, S, E, W.

Output

You are to output the game board on n separate lines, with m characters on each line. The m characters can be either . (to represent a non-obstacle position) or X (to represent an obstacle at that position). To disambiguate, you must draw the board so that the left side of the screen is west (and the right is east, and so on).

Sample Input

2
2
1
1
N

Sample Query Interaction

Forward

à Returns false

Right

 

Forward

à Returns true

Forward

à Returns false

Right

 

Forward

à Returns true

Right

 

Forward

à Returns false

 

Output for Sample Input

. .
X .