You are to write a program that reads a maze description (defined below) from a file and builds an internal representation of the maze. The program must then find a path through the maze that begins in the top left corner and exits the maze wherever possible. The program should print out the path from the starting point to the maze exit.

Implementation Requirements

1. Your program must use a stack to keep track of where it has been so as to backtrack. When the exit is found, the stack will contain the path from the start.
2. You must write the code to implement the stack; don't use some other Stack class.
3. Your stack must be a pure stack (only stack operations are allowed) - you can use the Java Stack class.

The maze description

The file containing the maze will have the number of rows and the number of columns on the first line of the file. Subsequent lines will contain the rows of the maze. The '*' character will represent a wall, a space character will represent the absence of a wall. For example, a maze file with 9 rows and 20 columns might look like the following (notice the exit is in the lower right):

9 20 ******************** * * * ** ** ***** ** ***** * * * * * * * * * * * * * * * * ************* ** * * ******************** 

Implementation Suggestions

Create a class Room. Each Room object would hold information about one room in the maze. Push the Room on the stack when you enter a room and pop it off when you leave. Record where you have been in each room.

Extra Credit

As always, you can get extra credit by going above and beyond the assignment. MAKE SURE THE ASSIGNMENT IS PERFECT before you do any extra credit. Some ideas include:

1. print out the maze and the path using Swing.
2. Write and use your own Stack class.
3. Something else that significantly adds to the assignment