Exploring a Maze

You are going to write a program that uses our new data structures, stack and queue, to explore a maze and, hopefully, find a way out of it. There are many algorithms that use different data structures and different strategies to explore mazes. In this assignment you will try two such approaches. In both of these approaches you will start from some initial position within the maze and evaluate the neighboring spaces until either you find a way out, or you discover that there is no way out. The rough outline of both approaches is to examine spaces around the current position and decide which need to be examined further and which definitely do not lead to an exit (more details below in the algorithm description).Given a maze and an initial position find your way out or decide that there is no exit.
You should be able to solve the above maze on paper easily. But how do you tell a computer to find a way out? The computer cannot just look at the whole maze and figure out where the nearest exit is. Think of yourself being stuck a maze without having a ”global” view. You only have a local view of what is immediately next to you and before you take a step it might be wise to decide if there ever might be a reason to come back to your current location. The algorithm below describes this type of search for a way out of a maze. You are going to keep a set of spaces that need to be examined (places that you might need to get back to in order to test another alternative). The exact representation of this set does not matter from the point of view of the algorithm. At the very beginning the set consists of a single space that is the initial position. We explore the maze by repeating the following steps: • if the set is empty, there is no way out of the maze - algorithm ends; otherwise • take the next element from the set – if the space that you just picked has been visited before, no need to look at it again, skip the rest of this step – if the space is a way out, you found the solution - algorithm ends – otherwise, examine all of the neighbors (the order does not matter, but for the purpose of this assignment always look at the neighbors in the clockwise order starting at the top as in the grid below)
The input file should be specified on the command line as the first argument. Make sure that you program verifies in the file exists and is readable before it tries to open it. The first line in the input file indicates the initial position. The position consists of two integers: first is the row number, second is the column number (numbering starts at zero). The remaining lines represent 2D maze. The maze consists of • walls, marked by ①’s in the input file, • corridors, marked by spaces in the input file, • ways out, marked by ♦’s in the input file.
You need to crest a class that represents a maze. The class should contain as a data field a two dimensional array of spaces. The maze should provide a toString() method that returns a string representing the entire maze. The toString() method for the maze should use the toString() method for each space. You should also provide methods that given a valid position in the maze • determine what type of space it is, • change the type of the space to a different one (specified by a parameter), • return a list of neighbors that are not walls (i.e., ones that you may need to explore further).
Attached is the solution