CCC '02 S3 - Blindfold

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 16M

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 the * character.

Sample Input


Sample Output



  • -16
    ALI989  commented on June 24, 2020, 11:56 a.m.

    This comment is hidden due to too much negative feedback. Click here to view it.

  • 35
    Encodeous  commented on Nov. 26, 2019, 12:15 p.m. edited

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

  • 7
    JimmyDeng12345  commented on Oct. 7, 2018, 1:56 a.m.

    how is this a 5 pointer??

    • -7
      maxcruickshanks  commented on June 20, 2020, 3:00 p.m. edit 2

      This comment is hidden due to too much negative feedback. Click here to view it.

    • 14
      Togohogo1  commented on Jan. 19, 2020, 11:12 p.m. edited

      This should be worth at least 7 points. Most of the other CCC S3's are all 7+.

      • 1
        Tommy_Shan  commented on Aug. 21, 2021, 5:17 p.m.

        This problem should be 10 or 10+ points

  • -11
    Bari_Sax  commented on Oct. 3, 2017, 1:27 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.

    • 22
      Tearful  commented on Oct. 3, 2017, 2:00 p.m.

      YOU DON'T