Maze (II) |
Johnny likes solving puzzles. He especially likes drawing and solving mazes. However, solving a maze he has drawn himself is too easy for him.
Since his computer is his best friend, he figures that he needs a program drawing the mazes for him. So he starts thinking about an algorithm performing this difficult task for him and he comes up with `Johnny's Simple Algorithm.'
You start with a M×N grid, where M is the number of rows and N is the number of columns of the grid. Initially, no two cells of the grid are connected to each other, so every cell is surrounded by walls on all four sides. The walls consist of an underscore (`_') for a horizontal wall, and a vertical bar (`|') for a vertical one. For example, if M = 3 and N = 4, the grid looks like this:
_ _ _ _ |_|_|_|_| |_|_|_|_| |_|_|_|_|
Every cell of the grid has unique coordinates (p, q). The lower left corner in the example is (1, 1), the upper right corner is (3, 4).
After choosing the dimensions of the maze, you choose a starting cell. From now on you keep track of a list of pending cells, which initially contains only one cell (the starting cell), and you repeat the following steps:
Johnny makes a nice little program using this algorithm and it works fine, but Johnny is not completely satisfied with the results. He is a demanding little boy and in his opinion the so-called branching factor of the maze is too low, i.e. the generated mazes contain very long paths and too few crossings. Therefore, the mazes are still too easy to solve for him.
A little trick can be applied to Johnny's Simple Algorithm, giving much better results. Johnny does not know it, but you will, since it will be explained below!
The idea behind the trick is to sometimes change the order of the cells in the list. This avoids
long paths and results in more branches. Changing the order of the cells in the list is done by
`flipping' part of the list. A flip can be specified by giving the position of a cell in the list (where
the first cell has position 1) and consists of reversing the sub-list starting at the specified cell and
ending with the last cell in the list.
For example, if the list consists of the following cells:
Now, we will reveal `Johnny's Advanced Algorithm.'
The algorithm is pretty much the same as `Johnny's Simple Algorithm,' only sometimes part of the list is flipped. The steps you repeat after choosing the dimensions of the maze, choosing the starting cell and adding this cell to the list are:
Since you are taking part in a programming contest, we ask you to write a program generating nice mazes for Johnny, using `Johnny's Advanced Algorithm,' to make him happy again. The maximum size of a maze is 39×39.
The first line of the input contains the number of test cases. The input for every test case is divided into three parts:
The input for each test case contains exactly the number of commands needed for that maze.
The resulting mazes should be printed using spaces (`'), underscores (`_'), vertical bars (`|') and end-of-line characters. No unnecessary whitespace should be printed. The mazes should be followed by one blank line.
2 3 3 1 1 U U R D D R U U 3 4 2 1 R U L F 2 R U R D D F 4 D L L
_ _ _ | | | | | | | |_|_ _| _ _ _ _ |_ | | |_ _ | | |_ _ _|_|