CS 302 Assignment 5:
Finding the shortest path through a maze using breadth first search.
Due date: Wednesday, October 7, 2009, midnight.
All programming assignments must be
submitted electronically.
Submit them to the graduate assistant,
Abhinav Dasu, by email at
dasun"at"unlv"dot"nevada"dot"edu
on or before the due date.
Your email must come from your engineering college (or computer science
or computer engineering) account.
Write a program which
-
Read in a maze, consisting of an binary array.
The number of rows will not exceed 40, and the number of columns
will not exceed 78.
-
Find the shortest path from the upper left corner to the lower right
corner, if there is one.
-
A path can only go up, down, or sideways (not diagonally) and must
only pass through zeros. The ones are walls.
-
Use a queue, and use the breadth first search
algorithm shown in class.
-
Here are some practice mazes:
maze01 and
maze05 and
maze06 .
maze07 .
maze08 .
maze09 .
maze10 .
maze11 .
-
Here are the outputs of my program:
out01 and
out05 and
out06 .
alternative output for maze06 .
-
You do not have to do it the way I did it, but you must
use the queue algorithm.
-
And, you must write your own implementation of the ADT queue.
You must not take the implementation of the ADT queue
from the standard template library, or any similar library.
The reason for this rule is that
you need experience designing your own data structure, and you don't
get that by simply grabbing one from the library.
Perhaps you think that you don't need that experience, since the
standard template library is available. But, you're wrong. Libraries
only contain things which are commonly used. They do not contain
the more complex data structures you will need to design for specific
applications in the future.