In this assignment you are to write a program that finds a path through a “maze”. The maze will be represented by a 2-dimensional array of ints. You will be given a starting point in the array that consists of a pair of ints <x,y>. In this pair, x represents the row coordinate of the starting cell and y represents the column coordinate of the starting cell.
Given a starting coordinate <x,y>, your program will construct a sequence of coordinates (beginning with <x,y>) that represents the path through the maze. As an example, consider the following maze that has a starting coordinate of <1,0>. An entry of 5 in this maze represents “solid rock” and you cannot “visit” a cell with that value. An entry of 0 in this array represents a cell that you can “visit”.
5 5 5 5 5 5
0 0 0 0 0 5
5 5 0 5 0 5
5 5 0 5 5 5
5 0 0 0 0 0
5 5 5 5 5 5
A successful run of your program with this array as input would thus output the sequence <1,0>, <1,1>, <1,2>, <2,2>, <3,2>, <4,2>, <4,3>, <4,4>, <4,5>
Your program will solve a maze problem by using a stack to keep track of those cells that have already been visited. Your program should thus proceed as follows:
- Change the value of the starting cell from a 0 to a 1. Make an instance of the Coordinate class that corresponds to the starting cell and push it onto the stack. This coordinate represents the starting or “current” cell. It’s the place at which you enter the maze.
- Do a clockwise search for the next cell to be visited. For a given cell there are at most 3 possibilities for “new” cells to be visited. Once a “new” cell has been found push a coordinate instance with the cell's coordinates onto the stack and change the value in that cell from a 0 to a 1. That cell becomes the “current cell”. If no “new” cell can be found, then you are at a dead end and must backtrack. Note that no “new” cell can be found if the only cell(s) found has (have) a value of 1. Backtracking is accomplished by popping the stack and designating the “current” cell as the one whose coordinate values match the values of the Coordinate instance on the top of the stack. When a search for the next cell to be visited after the “current cell” yields coordinate values that are outside the array, you are done. Note that if the entry cell is in the first row, your search will automatically take you outside the array. Thus, you must treat the entry cell as a special case.
You must use the Stack class sketched in class and that is now on D2L. This class is in a package called stackpackage and includes an EmptyStackException class. Your code should thus include the following at the top of the file
import stackpackage.*;
Since the Stack class is defined for Objects, you must define a class named Coordinate whose instances will get pushed onto the stack. The following code shows how you might do this.
You will get your input for this program from a file. The first line in the file will contain the number of rows for the array followed by a space followed by the number of columns for the array. Each succeeding line, except the last, will contain the values for the rows. Thus, a file for the array shown above would consist of the following lines:
6 6
5 5 5 5 5 5
0 0 0 0 0 5
5 5 0 5 0 5
5 5 0 5 5 5
5 0 0 0 0 0
5 5 5 5 5 5
1 0
Your program will read in the first line and construct an array dimensioned to the values in that line. Your program will then read in the rest of the lines (except the last) and populate the array with the values from each line. The last line in the file will contain a value that is the x coordinate of the starting cell followed by a space followed by a value that is the y coordinate of the starting cell. Once the file has been read into the array, your program should process the maze (the array) and print out the sequence of coordinates that constitute the path from the starting point to the exit point. Note that the printout must begin with the starting coordinate and must end with the exit coordinate – not the other way around.
Your program should be capable of solving a maze of any size
