-----------------------------------

SJ

Tue Feb 17, 2009 7:37 pm


[CCC] 2002 S3 Blindfold

-----------------------------------

I was looking over past contests and came across this problem

S3J5
Blindfold
Rose and Colin are playing a game in their backyard. Since the backyard is rectangular
we can think of it as a grid with r rows and c columns. Rose and Colin place obstacles on
some of the squares.
The game is played as follows:
Colin covers his eyes with a blindfold then Rose carries him to some grid square in the
backyard. She sets him down so that he is facing north, south, east or west. Colin does
not know this initial position or direction.
Rose then instructs Colin to make a series of m moves through the backyard. Each move
is one of: F - moves forward one grid square in the direction that he is facing,
or
L - turns 90 degrees counter-clockwise, remaining on the same square, or
R - turns 90 degrees clockwise, remaining on the same square.
After making these moves, Colin is standing at some final position. He must now figure
out where he is standing. You will help him by writing a program to determine all
possible final positions. Assume that Colin's initial position, final position, and all
intermediate positions lie within the backyard but never in a square that contains an
obstacle. You may also assume that Colin is always facing a direction that is parallel to
the sides of the backyard (north, south, east, or west).
The input begins with r and c (1