CS127 Assignment: Mazes

Due Wednesday, 1/17/01. Submit your maze.cpp, maze.h, and mazemain.cpp via HSP.

What you're going to do

For this assignment, you will write a program that takes a text-file representation of a rectangular maze and prints out the resulting maze, including a legal path from the upper left corner to the lower right corner of the maze.

You can start with the code in maze.h, maze.cpp, and mazemain.cpp. When compiled, this program will read a maze from the specified text file and print the resulting maze to standard output. See the comments in the source files for more details.

The maze file format

The format in which the mazes will be stored in text files is adapted from a format described in the problem set for the 2000 North Central Section of the ACM International Collegiate Programming Contest. The file format we will use is: 

		Number of rows
		Number of columns
		For each row, each square in the row is
			represented by a hexadecimal digit.


The hexadecimal digits are obtained like this:

		Start with 0
		If the square has a top wall, add 1
		If the square has a right-hand wall, add 2
		If the square has a bottom wall, add 4
		If the square has a left-hand wall, add 8
		Write the resulting number (0-15) as a hexdecimal
			digit (0-9, A, B, C, D, E, or F).
For example, a 2x3 maze with exterior but no interior walls (that is, an empty 2x3 room) would be represented by: 

		2 3
		9 1 3
		C 4 6
You don't have to parse this file format--that's what operator>> already does--but you might want to create example mazes for testing.

An example

Suppose you have a text file called maze.txt containing the following: 

	3 7
	3 B D 1 5 1 3
	A C 1 6 9 6 E
	C 5 4 7 C 5 5

Then your program, when run with maze.txt as a command-line argument, should print out the following: 

+---+---+---+---+---+---+---+
  * |   |     *   *   *     |
+   +   +---+   +---+   +   +
| * |     *   * | *   * |   |
+   +---+   +---+   +---+---+
| *   *   *     | *   *   *  
+---+---+---+---+---+---+---+

Here, the *'s mark the path from the upper left to the bottom right.

An algorithm

I want you to compute the solution of the maze using a stack and no recursion. Maybe later I'll let you do it recursively, but for now, I want you to manage the stack explicitly yourself.

Here's a pseudo-code algorithm that should do the job for you. To implement this algorithm, you'll need to make modifications to the MazeSquare struct and the Maze class.