CCC '02 S3 - Blindfold

View as PDF
Submit solution
Points: 15
Time limit: 1.0s
Memory limit: 256M
Problem type
Canadian Computing Competition: 2002 Stage 1, Junior #5, Senior #3

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 Specification

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

Output Specification

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

Sample Input

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

Sample Output

.*..
.XX*

Comments


  • 0
    踏雪寻梅  commented on March 31, 2024, 3:16 p.m.

    I would like to ask what are the tips for avoiding TLE ？？？？ I'm going crazy


  • 0
    xiaowuc1  commented on Oct. 7, 2021, 6:41 a.m.

    The original test data for this problem were misleading, with a maximum value of m = 50.

    Two test cases have been added with the maximum value of m = 30\,000, the time limit has been dropped to 1 second, and the point value for this problem has been increased from 5 to 10. All unlocked submissions have been rejudged.

    Further adjustments to this problem may result.


  • 75
    Encodeous  commented on Nov. 26, 2019, 5:15 p.m. ← edited

    How are you supposed to solve this question if you were blindfolded?