TopCoder problem "MazeReconstruction" used in TCHS09 Round 1 (Division I Level Three)



Problem Statement

    You are standing on a cell inside a maze, facing south. The maze is a rectangular grid where each cell is either passable or contains a wall. Each row and each column of the maze contains at least one passable cell. You walk through the entire maze, visiting every passable cell in every row and column. As you're walking, you write down all of your moves. Later, you want to draw a map of the maze using only your notes.

You are given a String moves containing your notes, where each character represents a single move. 'F' means that you walked forward one cell in the direction you're facing. 'L' and 'R' mean that you changed your direction by turning left or right, respectively, by 90 degrees, without changing your position.

Return a String[] containing the maze, where '.' denotes a passable cell and '#' denotes a wall. The j-th character of the i-th element must represent the cell at row i, column j of the maze, where row 0 is the northern-most row and column 0 is the western-most column.
 

Definition

    
Class:MazeReconstruction
Method:mazeMap
Parameters:String
Returns:String[]
Method signature:String[] mazeMap(String moves)
(be sure your method is public)
    
 

Constraints

-moves will have between 0 and 49 characters, inclusive.
-Each character in moves will be 'F','L' or 'R'.
 

Examples

0)
    
"RRFRF"
Returns: {"..", ".#" }
1)
    
"LFFRFF"
Returns: {"...", "##.", "##." }
2)
    
"LFLFRRFLFRRFLF"
Returns: {"#.#", "...", "#.#" }
You could have visited one cell several times.
3)
    
"FLFRFFRFFFRFFRFLFLL"
Returns: {"#..#", "....", ".##.", "...." }
4)
    
"FRFFFFFFLLFRFFFFFLLFRFFFFLFFLFF"
Returns: {"######.", ".......", "#.#####", "#.#...#", "#.###.#", "#.....#", "#.#####" }
5)
    
"FFFFFFFFFFFFFFFFFFFFFFFFLFFFFFFFFFFFFFFFFFFFFFFFF"
Returns: 
{".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
".########################",
"........................." }
6)
    
""
Returns: {"." }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10004

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13728&pm=10004

Writer:

Nickolas

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Simulation