CS 302 Assignment 4: Finding the shortest path through a maze using breadth first search.

Due date: Tuesday, March 12, 2013, midnight.

All programming assignments must be submitted electronically. Submit them to the graduate assistant by email on or before the due date at
androvas"at"unlv"dot"nevada"dot"edu
Your email must come from your engineering college (or computer science or computer engineering) account.
Your program must compile on the College of Engineering machines.
Write a program which
  1. Reads 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.
  2. Finds the shortest path from the upper left corner to the lower right corner, if there is one.
  3. A path can only go up, down, or sideways (not diagonally) and must only pass through zeros. The ones are walls.
  4. Use a queue, and use the breadth first search algorithm shown in class.
  5. Here are some practice mazes: maze01 , maze05 , maze06 , and maze14 .
  6. Here are the outputs of my program: output for maze01 , output for maze05 , output for maze06 , and output for maze14 .
  7. You do not have to do it the way I did it, but you must use the queue algorithm.
  8. 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.