Description
We want to write a program to generate mazes using minimum spanning tree methods. Our maze is a matrix of blocks. Each block can be a wall or a path. The ability to generate mazes is the key technique to develop computer games. We also visualize the maze using text.
Input
The first integer indicates the number of rows of the required maze matrix. This number is always odd.
The second integer indicates the number of columns of the required maze matrix. This number is always odd, too.
Next, a string of characters is the pattern we use to represent a wall block.
Next, a string of characters is the pattern we use to represent a path (i.e, non-wall) block.
Next, an integer indicates the number of edges that follow.
Each edge contains four integers:
the row index of the starting point,
the column index of the starting point,
the row index of the ending point, and
the column index of the ending point.
For example, 5 5 5 7 means an edge from (5, 5) to (5, 7) (which associates with a total of three blocks) in the maze.
These edges are associated to some randomized, distinct edge costs. The costs are omitted in the imput. Edges are listed in ascending order of edge costs in the input.
Output
Our maze is a matrix of blocks. Each block can be a wall or a path.
We create a maze by constructing the minimum cost spanning tree (MST) rooted at (1, 1) according to the edge cost order. In the matrix, tree edges are paths, and other places (except the entrance and exit at the first column in the second row and the last column in the second last row) are walls. MSTs can be obtained using Kruskal's, Prim's, or Sollin's algorithms as described in the textbook. Since edge costs are assigned distinct and are totally ordered, any algorithm should result in the same MST. If you have no preferences, the Prim's algorithm could be relatively easier to implement.