Example Run

Below is an example execution of your program. Both versions $($the unsolved maze and the solved maze$)$

should be output, one after the other.

$>$ java MazeDriver mazeOne.txt $"$In this assignment, you will use Stacks, Queues, and other Java collections to discover if a maze has a

solution $($or path$)$ from an starting point to an ending point.

Objectives

For this assignment, your objective is to create a program that will read in a maze definition in a specified

file format. The program will accept input via command line arguments. The command line argument will

be the name of the file from which to read the maze definition. Given that information, the program will

attempt to find a path between the start and exit.

You must follow the algorithm described in the instructions!

Not all mazes will have a valid path. If this happens, indicate to the user that no solution exists. Some

mazes will have more than one path out. In this case you program should print only one of them.

Instructions

To solve this problem you must use Stacks, Queues, and arrays. DO NOT USE RECURSION!

Start by finding all the locations possible to move from the starting location. For each possible location,

create a stack and push the start location and the new location onto that stack. Add each of these stacks

onto a queue $($creating a queue of stacks$).$

Next remove the first item from your queue $($this item is a stack$).$ Look at the top location of this stack and

compare it with the exit location. If they are the same, then your stack contains a path from the beginning

to the end of the maze. If the location is not the exit find all the possible locations that are $1$ step away

from the top location. For each of these new locations you just found, create a copy of the current stack and

push the new location on it$.$ Then enqueue all the newly created stacks onto the queue. You will stop this

process when the queue is empty or when you have found the exit.

You must keep track of the locations you have already checked in a data structure, otherwise an infinite loop

will result.

Your program should throw an exception $($with a helpful error message$)$ if the maze definition file specified

cannot be opened or does not exist.

Maze Definition File Format

The program will expect to read mazes in from files in the following format:

In the diagram above,

The first line is the max rows and max columns

The W represents Walls

The X represents an Exit

The E represent the Entrance

The space character represents an open space"

Help me come up with a logic that is in runMaze$()$ so that it solves the maze