### 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

**Problem Types:**[Show]

**Languages Allowed:**

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

## Comments (Search)

XIAOAGEon Nov 25, 2015 - 12:56:45 am UTC Dont calculate the complexity for this problem!!!!!!!!!!!!!!!!!!!!!!!!!!!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

spencereiron Nov 25, 2015 - 12:28:07 pm UTC Re: Dont calculate the complexity for this problem!!!!!!!!!!!!!!!!!!!!!!!!!!!XIAOAGEon Nov 26, 2015 - 2:37:37 am UTC Re: Dont calculate the complexity for this problem!!!!!!!!!!!!!!!!!!!!!!!!!!!Just giving word of advice to people who struggle with complexity like me :)

spencereiron Nov 26, 2015 - 2:51:43 am UTC Re: Dont calculate the complexity for this problem!!!!!!!!!!!!!!!!!!!!!!!!!!!zzh8829on Aug 25, 2012 - 5:49:47 pm UTC Finally