Using a Union-Find data structure (coded as a seperate class), create a program that generates nxn sized mazes. Each square in the maze is bounded by four positions: right(1), bottom(2), left(4) and top(8). Each position may have a wall, or may be open. Each square in the maze can be represented by one hex digit (0, 1, 2 ... F). (For example, 'D' is a square with walls to the left, right and top and 'F' is a square surrounded by walls.) Note: See the Hex Maze class houndout for further explanation. Your program should accept n as a command line parameter. The minimum allowed value for n is three -- check for bad values and terminate the program with a reminder. Your program should output (the only output of your program) a nxn block of hex characters (no spaces) that represent the maze to STDOUT. Initially, the maze should have a 'start' at the top left, an 'exit' at the bottom right, and walls around every other square. (For example, a 3x3 maze to be generated would be initialized as "BFF", "FFF", "FFE".) The walls in adjacent squares must match. (For example, the sequence "69" could appear in a legal maze, but not "6D".) In the resulting maze, every square should be 'reachable' from every other square. (For example, "A9D", "C03", "76A" is a legal 3x3 maze.)

MAZE GENERATION

Each square in the maze should be represented by an individual element in your Union-Find data structure. Use a numbering scheme for the squares such that you can tell which squares are adjacent. Select two adjacent squares and union them if they are not already in the same set at the same time that you "knock out" the walls between them (by adjusting the value 0-F of each of the two squares.) Repeat until there is only one set. At this point every square in the maze is mutually reachable. Some techniques to do this efficiently will be discussed in class.

IMPLEMENTATION

The Maze Generation logic should have its own class, as should the Disjoint Set. You probably want a seperate main function to handle the minimal i/o (main.cpp)

TESTING HINT

Short of finding a path from start to end (assignment 8,) or from the start to every square in the maze (which is even trickier,) how can you verify that your maze is valid? Smaller mazes can be checked visually using one of the programs provided. Larger mazes can be partially checked. Verify that no squares are 'F' and check each adjanced pair of squares to make sure that they are in agreement about the presence or lack of a wall between them. Make sure that all the exterior walls are in place (except for the opening for the start and the finish.)

RG-HT 2 LEFL 8 10 1),12/13,14,/5 BoTTOW 23,7, 19, ll, 191S 7 ASC 9 A DSUST o A a -z97 122 87 A-Z 65 10 55 11 B Lega Maze 3) A q D 7 6 A 12 C Le Paie 13 6 9 IS F L00 FFF Legal 5x Maze aze 6 8 A B 8 3 5 5 5 O A 3 5 RG-HT 2 LEFL 8 10 1),12/13,14,/5 BoTTOW 23,7, 19, ll, 191S 7 ASC 9 A DSUST o A a -z97 122 87 A-Z 65 10 55 11 B Lega Maze 3) A q D 7 6 A 12 C Le Paie 13 6 9 IS F L00 FFF Legal 5x Maze aze 6 8 A B 8 3 5 5 5 O A 3 5