CS127 Assignment due Monday, 1/27/03

CS127 Assignment: Mazes

Due Monday, 1/27/03. 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.

Initialize: Mark all squares as "unvisited." Mark square (0,0) (i.e. the upper left square) as visited. Push (0,0) on a stack of squares.
Test: If the stack is empty, END.
Otherwise, let T = the top square on the stack. If T is the bottom right square of the maze, END.
Move: If all squares adjacent to T (i.e. the squares up, down, right, or left from T--no diagonal adjacency) are either blocked from T by a wall or are marked visited already, POP the top item from the stack.
Otherwise, select a square S that is adjacent to T, unvisited, and accessible from S (no wall between them). Mark S as visited and push it on the stack. Go to Test.

Notes

If your maze has more than one solution, your program should just display one solution. The program should definitely halt, however.

If your maze has no solutions, your program should halt, printing the maze with no *'s.

If you make some good test mazes, share them with each other. Putting together the text form of a maze is kind of a pain.

Have fun, start early, and keep in touch.

Jeff Ondich, Department of Mathematics and Computer Science, Carleton College, Northfield, MN 55057, (507) 646-4364, jondich@carleton.edu