EECS 560 Lab 10 solved

 For this lab you will implement the union-find data structure in order to build a maze.   The basic idea is that you start with a grid like that in the diagram on the left below in which the entrance is in the upper left corner and the exit is in the lower right.   Initially, each region (cell in the grid) is given a number and put into a set by itself.   You will randomly knock out a wall between two cells if those cells are not already in the same set.   The algorithm terminates when you are left with one set containing all cells.   The example in the diagram on the right below illustrates the situation after some walls have been removed.

Since each cell has four walls, you must systematically “number” the walls so you can randomly generate the wall to be removed (i.e. you must use the random number generator).   Keep in mind there is no wrap-around so the walls on the top, bottom, left, and right sides should never be removed since such a removal would not connect two adjacent cells.

Your program must permit the user to enter the dimensions of the grid, which is not necessarily square (e.g. it could be 5 ´ 10).   After generating the maze your program should print it out.   (Just the maze, not the numbers in the cells should be printed.) Hand in your program, at least two sample runs, one of which is not a square grid, and one of which has dimensions greater than or equal to 12 x 12. Be sure to include any instructions needed to run your program.   The union-find data structure as described in class and in the text must be used to receive credit.

Due dates:   Sunday night before midnight.