Project 1 -- EECS380 -- Winter 2001
Maze solver -- ``The quest for cheese''
Originally Due Monday Feb 19th at 6pm.
Due date extended to Friday Feb 23rd at noon.
For this project you will write a C++ program which routes a mouse (actually
Oliver the Mouse) through a maze to find the cheese. You will develop a
number of algorithms for solving the maze and will be graded on correctness,
programming style, and speed of execution.
The Maze consists of open areas (indicated by blank spaces), walls
(indicated by `X'), where Oliver starts (indicated by `O') and where the
cheese is (indicated by `C'). Oliver, being a fairly simple mouse, can only
travel north, south, east or west. He may not travel along the diagonals of
the maze. Your task will be to indicate the route from Oliver to the cheese
by drawing the route using the `*' symbol. So a sample maze might look like
While the output might look like:
X * XXX
The maze will be a square of fixed size (N by N) and Oliver is not allowed
to leave the bounds of the maze.
Sample mazes have been posted as handouts.
You are to develop three routing schemes for Oliver.
In the queue-based routing scheme you are to have a queue of maze locations.
Place the location that Oliver starts at in the queue. And then do the
- A queue-based routing scheme
- A stack-based routing scheme
- An ``optimal'' routing scheme
For the stack-based routing scheme, do the same thing, but push and pop the
locations rather than enqueueing and dequeueing them. Clearly you will need
to expand on the above algorithms, but you must follow the basic algorithm
outlined above for the queue and the stack-based routing algorithms.
- Dequeue the next location.
- Enqueue all locations next to the location you just dequeued which are
empty spaces (blanks) that have never before been enqueued. Remember that
Oliver can only travel north, south, east or west, so diagonal spaces are not
considered next to each other. As you enqueue these spaces, check to see if
any of them hold the cheese. If none of them do, go back to step 1.
- Clearly you have found a route from Oliver to the cheese, but exactly
what that route may not be clear to poor Oliver (or yourself!) So you need
to figure out what route Oliver should take. Your route should not
backtrack onto itself. That is, it should not require Oliver visiting the
same square twice.
For the optimal routing scheme, you are free to use any routing algorithm
you wish to run. But you must get Oliver to the cheese in as few steps as
possible AND you will be graded on how long it takes you to find
Oliver's route. The first goal is getting an optimal route. Finding a
non-optimal or illegal route (going through walls, outside of the Maze,
etc.) quickly is worth nothing, even if it is fast...
Input and Output formats
Your program should be able to deal with two different input and output
formats. The first is a coordinate scheme where Oliver, the Cheese, and
each wall are listed by their XY-coordinates. Any unspecified location is
assumed to be empty. The second is a map where the
XY coordinates are implicit by their ordering. In both cases the size of
the maze is specified on the first line as a single integer ``N''
representing an N by N maze. For example the following is a legal map-formated Maze:
While that same Maze could be specified in the coordinate scheme as:
X 0 0
X 0 1
X 0 2
X 0 3
X 3 3
O 1 0
X 2 0
X 1 2
C 1 3
The output file formats are very similar. For the map format simply add the
``*'' as needed to specify the path in addition to reprinting the rest of the
map. For the coordinate solution specify only where to place ``*''s.
So for the above Maze one might get:
as the map format and that same solution could be represented using the
coordinate output as:
* 1 1
* 2 1
* 2 2
* 2 3
In the event of the coordinate solution the path should specify each step
taken starting next to Oliver and ending next to the cheese.
In either case, if no route exists your program should print an informative
message to standard error, exit(1), and leave the output file blank.
When you are asked to time your program, you should measure the time it
takes for your search algorithm to run. Do not include the time it takes to
read the input or write the output. HOWEVER you must include the time for
the entire search algorithm including figuring the exact path taken. Don't
try to bend the rules here (by starting the search while reading in the
data), doing so will result in 0 points for the timing
part of the grade (see below).
Timing information reported should be printed to standard output in
the following format:
where X is some base-10 number.
You should do this by using the following command:
cout << endl << "@@@ runtime=" << X << endl;
Where X is a double.
Stacks, Queues and the STL
You are to write the program using your own stack and queue classes. Those
classes should have the same interface as the stack and queue classes in the
STL. Further, you will also be expected to use the STL rather than your own
stack and queue implementation. You only need to write the member
functions for queue and stack that you actually use!
To be able to experiment with different implementations of the same
interface, (stack and queue) you need to do the following:
When you submit your project, you need to have -DSTLon set in the Makefile. The
autograder will run your code that way to test how it uses STL, then remove
-DSTLon from the Makefile and run the code to test how your containers work.
The code should work identically (constant-factor differences in speed are
allowed). None of your code should ever perform a
- Have the alternative container classes available (each class must have a
Note, you need not use the same names as above (e.g. Proj1STLContainer).
- Implement your code that uses containers in terms of an alias
Example: Container (in other words, Container will be the class name
assumed by your code, even though no such class was defined yet).
- Use the typedef command to make the alias point to one of the actual
typedef Proj1MyContainer Container;
should go after your #include the headers of your container
- In order to change how the code is compiled, depending on the
container implementation you need, use
typedef Proj1STLContainer Container;
typedef Proj1MyContainer Container;
(The # should be in the first column of your code and not indented.)
- STLon is a "macro" or a "symbol" that, when defined, will make your
code use an STL-based container. Otherwise, your own container will
be used (but the code implemented in terms of "Container" will be
- To define STLon, modify Makefile and add
-DSTLon after g++. This has
the same effect as adding
#define STLon 1 to your code (before
#ifdef), except that your code is not modified.
#define STLon. If you want to better understand what all of this
read the man pages for
cpp and the -D flag for the g++ compiler.
Additional suggestions can be found in the
Command line arguments
Your program should take the following command line arguments: (when we say
a switch is "set" that means it appears on the command line.)
Legal command line arguments must include exactly one of -Stack -Opt or -Queue. If
none are specified or more than one is specified the program should print an
informative message to standard error and exit(1).
- -Stack (boolean) If this switch is set you should use the stack-based
- -Opt (boolean) If this switch is set you should use your optimal
- -Queue (boolean) If this switch is set you should use the queue-based
- -Infile (string) Use the string as the input filename. If the -Infile flag does
not appear then you should use the file ``maze.txt'' as the input filename.
- -Outfile (string) Use the string as the output file name. If the -Outfile flag does
not appear then you should use the file ``mazeout.txt'' as the output
- -Time (boolean) If this switch is set, print the runtime of your program as
- -Incoordinate (boolean) If this switch is set, the input file is in the coordinate
format. If the switch is not set, the input file is in the map format.
- -Outcoordinate (boolean) If this switch is set, the output file is to be in the
coordinate format. If the switch is not set, the output should be in
the map format.
- -Help (boolean) If this switch is set your program should print a brief
help message which describes what the program does and what each of the
flags are. The program should then exit(0).
Sample inputs and outputs
Using the stack based algorithm put with the map format for input and output:
should result in:
And using the queue algorithm with the coordinate input and output:
Should result in:
O 3 7
X 4 5
X 4 6
X 4 7
X 4 8
X 6 6
X 6 8
X 6 9
C 8 7
* 3 8
* 3 9
* 4 9
* 5 9
* 5 8
* 5 7
* 6 7
* 7 7
Errors to check for
In all these cases, print an informative error message to standard error and
- In the map input format you should check for: illegal characters, maps
which are too short, (either not enough characters per line or not enough
lines), and those don't start with a number by itself on the first line.
- For the coordinate input format you should check for: illegal characters
in the first column, coordinates which would not fit in a maze of the stated
size, and those that don't start with a number by itself on the first line.
- Not being able to open the output file for writing.
- Not having exactly one of -Stack -Opt or -Queue on the command line.
What you don't need to check for
- For the map format ignore any extra characters on a given line, or on
lines below the last line needed.
- For the coordinate format, assume that the data is really in the correct
format. (ie. character integer integer) You don't need to
error check that. (Although you do need t check to see if the character and
the integers are valid as mentioned above.)
How to turn things in
First of all, be 100% certain that your code works on a SUN workstation
That said, do all of your work, with all needed files, in some directory
other than your home directory. Before you turn in your code be sure that:
- You have deleted all .o files and your executable(s), e.g., by typing make clean
- Your makefile is called
- Typing the command
make will generate an executable called
- You have the makefile set up to use the STL and have followed the rules
outlined in the section Stacks queues and the STL, above.
- You don't have any unneeded files or other junk in that directory or any
of its subdirectories.
- Go to one level above the the directory with your code (and makefile,
/afs/engin.umich.edu/class/perm/eecs380/bin/submit380 1 DIRNAME
where DIRNAME is the name of the directory in question. The program will
verify that you wish to turn your code in, and that's it.
You should receive some feedback indicating that the program was received and
that things seem to be in working order. If you do not get that feedback
within 30 minutes, please contact Prof. Brehob at firstname.lastname@example.org.
You will not receive a grade from the autograder. Once the due date has passed we will
grade your code (both with an autograder and by hand). The last thing you
turn in is what we will grade.
So why are we doing things this way? There are many reasons. We clearly
need to have an autograder of some type, there is no way we can grade so
many student's projects for correctness by hand. This frees us up to look
at coding style and algorithm issues. At the same time, giving the students
complete autograder feedback makes the debugging process unrealistic. It
will be very rare indeed when you have some way to validate that your code
is 100% perfect (or at least as perfect as it needs to be). As such we are
providing just enough functionality to insure that you are getting the
basics right (compiles, runs, gets some trivial cases correct, etc.) but not
so much as to take away the need to carefully test your own code.
The program submit380 should be available starting Feb 6th. (changed)
- Use a reasonable organization for your overall program.
- Find a fairly reasonable class structure. Don't stick everything into
one class. Make reasonable use of constructors. Where needed be sure to
supply a custom destructor. If the way you design your code feels sloppy to
you, it probably is. Utilize multiple files in a way that is consistant
with the general use in C++. Our text does a good job describing this.
- Use reasonable comments.
- Explain what each class does and what each data
member is used for. A one or two line description of most member functions
is also desirable. Where you use non-standard coding techniques, document
them. List your name and the date last modified for each file.
Remember that a useless comment is worse than no comment at all.
int temp; // declare temp. variable
would be an example of a useless comment which just makes code harder to
- Use reasonable formatting.
- It should be obvious where a given code block ends due to indentation.
Use reasonable and informative variable names. On systems where the program
"cb" (C beautify) is available, consider using an indentation style similar
to what it generates. Avoid lines that wrap in an 80 column display
- Variable names
- Using things like "i" and "j" as variables can be reasonable, but you
should not use such variables to store meaningful long-term data. Other
than LCV (loop control variables) you should use descriptive names for your
variables, functions, classes, structures, etc.
- Code resuse
- If you find yourself rewriting basically the same algorithm many times,
stop and try to see if you can somehow reuse the code.
Further, poor coding style will result in potentially significant deductions.
Follow the above rules as closely as possible.
- Working stack and queue algorithms using your own classes -- 50 points.
- Working stack and queue algorithms using the STL -- 25 points.
- A working optimal algorithm. -- 15 points
- The speed of your optimal algorithm -- 10 points
Hints and advice
- You may print whatever you want to standard output as long as none of
your output (other than the runtime) includes the string ``@@@''.
- You shouldn't print to standard error unless there is an error.
- If the program does find a route, be sure to exit(0) (or have main
return a 0).
- For the ``map'' format you might want to find a good way to read in a
whole line at a time. Trying to parse by ``word'' will result in a lot of