CCO '02 P3 - Return To Blind Man's Bluff

View as PDF

Submit solution


Points: 12
Time limit: 2.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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 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 5 \times 5 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.

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 Specification

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 \le r \le n) on one line, followed by your starting column position c (1 \le c \le m) on the next line. The fifth line will contain the starting orientation: that is, one of the characters, N, S, E, W.

Output Specification

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

Operation Result
Forward → Returns false
Right
Forward → Returns true
Forward → Returns false
Right
Forward → Returns true
Right
Forward → Returns false

Sample Output

. .
X .

Comments

There are no comments at the moment.