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:
- procedure Right()
turn right 90 degrees in the playing area
- procedure Left()
turn left 90 degrees in the playing area
- function Forward() : integer
move forward and return 1 if there is no obstacle or wall
in the position immediately (1 unit) in front of you.
Returns 0 and does not change position or compass orientation if there
is a wall or an obstacle 1 unit in front of you.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
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 Sample Query Interaction
2
1
1
N
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Output for Sample Input
. .
X .