TopCoder problem "MazeImprovement" used in TCO '03 Semifinals 2 (Division I Level Two)



Problem Statement

    

Consider a maze laid out on a rectangular grid. Each node in the grid is connected to some or all of its neighbors in the four cardinal directions (north, south, east, west). A set of connections qualifies as a maze if (1) all nodes are reachable from the northwest corner, and (2) there are no loops. You may recognize these conditions as defining a spanning tree of the underlying grid.

It is easy to construct a random maze using, for example, a randomized version of Kruskal's algorithm. But mazes generated in such a fashion are often aesthetically unappealing. The problem is that such mazes contain too many short deadends. A node is called a deadend if it is connected to exactly one other node, a corridor if it is connected to exactly two other nodes, and an intersection if it is connected to three or more other nodes. A short deadend is a deadend that is connected directly to an intersection, with no intervening corridors. For example, consider the following maze:

      A  B--C--D--E
      |     |     |
      F--G--H  I--J
                  |
      K--L--M--N--O
This maze contains four deadends: A, B, I, and K. B and I are short deadends because they are connected directly to intersections (C and J, respectively). A and K are not short deadends because they are connected to corridors (F and L, respectively). The problem with short deadends is that human solvers can immediately see that there is no point in exploring them, so such nodes are viewed as "wasted space".

Given a random maze, there is a simple transformation that can greatly improve the aesthetic appeal of the maze by eliminating many short deadends. The idea is that, whenever a short deadend is adjacent in the grid to another deadend (not necessarily short), the short deadend can be disconnected from the intersection it is currently connected to, and reconnected to the other deadend. For example, in the above maze, node B can be disconnected from C and reconnected to A, yielding the new maze

      A--B  C--D--E
      |     |     |
      F--G--H  I--J
                  |
      K--L--M--N--O
Now B is no longer "wasted space". Instead, B now contributes to the difficulty of exploring the path that used to end at A. Node I is still a short deadend, but it cannot be eliminated by this transformation because it is not adjacent to any other deadends.

Call a short deadend a candidate if it is adjacent to another deadend. You are to eliminate candidates one at a time using this transformation until there are no more candidates. At each step, you should eliminate the northernmost candidate. In case of a tie, eliminate the westernmost of the northernmost candidates. When a candidate is adjacent to two or more other deadends, it should be reconnected to a short deadend if possible. In case of a tie, the candidate should be reconnected to the northernmost of the tied deadends. If there is still a tie, the candidate should be reconnected to the westernmost of the tied deadends.

The initial maze will be given as a rectangular String[]. The rows are ordered from north to south, and the columns are ordered from west to east. Each character describes the connectivity of the node in the corresponding position in the grid. The meanings of the possible characters are as follows:

  • '|' means the node is connected to its northern neighbor
  • '-' means the node is connected to its eastern neighbor
  • 'L' means the node is connected to both its northern and eastern neighbors
  • '.' means the node is connected to neither its northern nor its eastern neighbor
Note that all connections are two-way.

For example, the maze

      A  B--C--D--E
      |     |     |
      F--G--H  I--J
                  |
      K--L--M--N--O
would be represented as
      .---.
      L-|-|
      ----|

You are to write a method that will take an input maze, apply the described transformation, and return the resulting maze, in the same format as the input.

 

Definition

    
Class:MazeImprovement
Method:improve
Parameters:String[]
Returns:String[]
Method signature:String[] improve(String[] maze)
(be sure your method is public)
    
 

Constraints

-maze contains between 2 and 50 elements, inclusive.
-Each element of maze contains between 2 and 50 elements, inclusive.
-All elements of maze contain the same number of characters.
-Elements of maze contain only the characters 'L', '|', '-', and '.'.
-No 'L' or '|' appears in element 0 of maze.
-No 'L' or '-' appears as the last character of an element of maze.
-The maze described by maze is connected (ie, all nodes are reachable from the northwest corner) and has no loops.
 

Examples

0)
    
{ ".---.",
  "L-|-|",
  "----|" }
Returns: { "-.--.",  "L-|-|",  "----|" }
The example above.
1)
    
{ 
  "........",
  "LLLLLLL|",
  "||||||||"
}
Returns: { "-.-.-.-.",  "-L-L-L-|",  "|-|-|-||" }
The maze
  A  B  C  D  E  F  G  H
  |  |  |  |  |  |  |  |
  I--J--K--L--M--N--O--P
  |  |  |  |  |  |  |  |
  Q  R  S  T  U  V  W  X
becomes
  A--B  C--D  E--F  G--H
     |     |     |     |
  I--J--K--L--M--N--O--P
  |     |     |     |  |
  Q  R--S  T--U  V--W  X
2)
    
{ "--.--.",
  "|.-L.|",
  "|L-|-.",
  "L--L-|" }
Returns: { "--.--.",  "|.||-|",  "|L-|-.",  "L--L-|" }
3)
    
{ "....-.--....-..",
  "|LLL.L||-|L|L-|",
  "L-L-.-|L-|.LL..",
  "-|-||---.|L||.|",
  "-.-.LL-.LL|.LL|",
  "-L|L||-|||L|L.|" }
Returns: 
{ "..-.-.-.-.-.-..",
 "|L-||L||||L.L-|",
 "L-L-.-|L-|.L|..",
 "-|-||---.|L||||",
 "-.-.LL-.LL|.LL|",
 "|L|L|--|-|L|L-." }
4)
    
{ "--.-..--.----.--.--.-..-...-..",
  "-.LL-L-L.L---.L-.--LL-|-|LL-||",
  "-|-L-.L---||L--||--L--.||---L|",
  "L.-.--||-||L.|-|--L.L-.|-L.|||",
  "-|.L|-L.-L--..L.|L.||L-L.-.|L.",
  ".LL-||L--.|-.L|LL-.||-|-|L.|-.",
  "L.|-|-||L.-|-|...||--L.|-L-|-|",
  "|L.||-|..-L.|-LL|.---.||L-.-||",
  "L---..L|L-.L--.L.|L---L--|.L-.",
  "--|-LL||||L.|-.L-L|.L---.|LL.|",
  "|--|.|.-|||-L|L-|L.||L.---||L.",
  "||-LL-L||||--L-.|L.L-L--||||-|" }
Returns: 
{ "--.-.--..----.--.--.-..-.-.-..",
 "-.LL---L|L--.|L-.--LL-|-|L--||",
 "-|.L-.L---||L--|||-L--.|.---L|",
 "L.L.--|--||L..-|--L.L.||L|.||.",
 ".|.L|-|--L--.|L.|L.||L-L.-||L|",
 "|LL-||L-.-|-.L|LL-.||-|-|L.|-.",
 "L..-|.|.L.-|-|-.-.|--L.|-L-|-|",
 "|L|L.L||--L.|--L|.---.||L..-||",
 "L---..L|--.L--.L.|L---L--||L-.",
 "--|-LL|||||.|-.L-L|.L----.LL.|",
 "|--|-|.-|||LL|L-||.|||----||L.",
 "|L.L--L|-||--L--.L|L-L--|-||-|" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4707&pm=1782

Writer:

vorthys

Testers:

lbackstrom , brett1479

Problem categories:

Simulation, String Manipulation