2002 Canadian Computing Competition, Stage 1

Problem J5/S3: 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).

Input

The input begins with r and c (1 ≤ r ≤ 375; 1 ≤ c ≤ 80 ), each on a separate line. Next are r lines of c characters describing the backyard: a period character denotes a grid square that Colin may walk through; a capital X character denotes a grid square with an obstacle. Below the grid is the number m (0 ≤ m ≤ 30000) followed by m lines describing Colin's moves. Each line has a single character: F, L, or R.

Output

Your program should output the backyard grid, indicating all possible final positions with the * character.

Sample Input

2
4
....
.XX.
3
F
R
F

Sample Output

.*..
.XX*

All Submissions
Best Solutions

Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 02, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

This problem sucks

They put the m can be as large as 30000. Well, I know junior competitor doesn't calculate the complexity, but the problem is also in senior, where people do think about complexity

O(r*c*n) CAN pass..............................

test data so weak

S3 isn't usually the most difficult question to pass. A brute force algorithm should usually do it with ease. Also, what do you expect from a simulation problem?

I'm just saying that m value in test cases are way less than 30000. It's very misleading for people who calculate the complexity before coding.

Just giving word of advice to people who struggle with complexity like me :)

Fair enough!

Nice! The last one with 5||3 points.