Maze Solver

Due May 18, 2003 at 8pm

In this assignment you will implement the guts of a program to find the shortest path through any maze. This is not as hard as it sounds, and we have implemented much of the necessary support code, and outlined what you have to do to write the solve function.

You will want to read about how to search for the shortest path in a maze.

The Assignment

We have written a class for the Maze cells, one for the Queue, and one simple class Point that lets you have ordered pairs (x, y). We provide the main function, which loads in mazes, and a function to print out mazes. All you must do is to fill in the functions solve and backTrack. An outline of what each function should do is provided in the code itself. The code and a Makefile for it is available for download here. The only file that you need to alter is maze.cc, although you may change anything you like other than the Makefile, so long as your program still works properly.

UPDATE (5-10-03): There was a slight bug in maze.cc. Download a new copy below, or change "width" in the for loop near line 64 to be "height".

Also, the maze2.input maze2.output samples have been altered slightly (although if you passed them before you will still pass them now, they are just easier to pass now.)

Input / Output
Input is handled entirely by the skeleton code we have provided. Do not alter this code, and the input should be fine. You will almost certainly NOT want to do any input by hand, so make sure you understand the use of the file-redirection operator "<" under Linux (which will be explicitly covered in lab in the coming weeks.) In short, create input files with the format used in maze1.input and maze2.input, below. When invoking your program on the command line, use 
./maze < mytest.input
Where "mytest.input" is the name of your input file.

For output, we expect one of two behaviors for any maze. If the maze is solvable, print out the maze (using the provided function, with the path between S & D marked with the character "X". Since there can be more than one path of minimal length for a given maze, you are only responsible for printing out one of them.

If the maze is unsolvable, print the string "No solution.", followed by a newline, and terminate.

The functionality of your program will be automatically graded, so if your output varies from this at all, you will be graded off by at least 10%. Here are two sample inputs and outputs:

maze1.input maze1.output
maze2.input maze2.output

You can test the proper output of your program under Linux by running the following: 
./maze < maze1.input | diff - maze1.output
./maze < maze2.input | diff - maze2.output
If either of these commands produces any output, then your program did not produce the correct output.

If your program does not pass at least these tests, then it is not complete. There are more complicated tests which we will use, so do not assume that passing only these tests guarentees you full credit. It is up to you to make sure that your program is fully tested.

Submission

You must submit all source files, whether edited or not. There is no reason for you to add any files or change their names, so we will use a standard Makefile for compiling your submissions. We will be using the compilation flags -Wall -Werror -pedantic, so any warnings your code generates will cause compilation errors, and a corresponding reduction in credit.