You are to write a program that can solve any square maze. You will be given a Stack template class to use in writing this program. With a template, you can construct a Stack of almost any data type that you want. The Stack template definition and implementation are in the file STACKCLS.H, available through 310LIB, O:\JLW\310, or L:\JLW\310. This file provides standard stack member functions: IsEmpty(), IsFull(), MakeEmpty(), Push(item), Pop(), and Peek(). You are NOT allowed to change the contents of STACKCLS.H in any way; You ARE required to use the Stack template provided in this file in your program. Also, although recursion might be appropriate in this program, you are NOT allowed to use it - you must do your own Stack manipulation.

Your program should prompt repeatedly for a data file specification and read in the maze contained in the file. On an invalid file spec, the program should terminate. On the first line of the data file is a number, m, (<= 25) that specifies the size of a square maze. Then, on m subsequent lines there are m characters each that define the maze, one character per position with \n at the end. Each blocked maze position is marked by an asterisk; each open position is marked by a blank. The character 'S' marks the starting position; the character 'G' marks the goal. If the goal can be reached via open positions, your program should output the maze with the route between S and G marked with periods. Otherwise, the program should output a message saying there is no route and display the maze. Here is an example of the input data and a possible solution to the maze. NOTE: THE MAZES BELOW ARE STRETCHED HORIZONTALLY TO MAKE THEM SEEM MORE SQUARE.

Data					Solution
7
* * *   *   *				* * *   *   * 
S *     *   *				S *     *   *
  *   *     G				. *   *   . G
        *   *				. .     * . *
*   * *     *				* . * * . . *
          * * 				  . . . . * *
* * *   * * *				* * *   * * *

To have your program navigate through a maze, it will have to be able to move left, right, up, or down in open positions (no diagonal moves); it will have to remember where it has been (so it doesn't just oscillate); it will have to recognize when it is in a blind alley (and get out); and it will need to record the path between the start and the goal. A Stack is ideal for letting you handle most of these problems.

In addition to STACKCLS.H, there are five maze data files available to test your program - MAZE1.DAT, MAZE2.DAT, MAZE3.DAT, MAZE4.DAT, and MAZE5.DAT. All are in the same location as STACKCLS.H. Hand in a disk with your program in a you-P4.CPP file. Also, hand in a printout of your program.