CECS275 Project 4-Stacks & Queues Solved

Project 4 –

Maze Solver – Create a program to solve a maze using a stack and a queue (also known as Depth First Search and Breadth First Search). Allow the user to choose from 4 (or more if you’d like to create your own) different mazes that are read in from a text file, and then allow them to choose how to solve the maze. At the top of the text file are two numbers, they are the height and width of the maze. The possible characters in the maze are: ‘*’ – represents a wall, ‘ ‘ – represents a movable space, ‘s’ – represents the starting location, ‘f’ – represents the finish.

Point Class – Create a class point that has an x and y location. Set the values through the constructor, create methods to get the values.

STL Stack and Queue – Use the STL stack and queue for the DFS and BFS. These should store type Point.

MazeSolver – Your main function should do the following:

1. Allow the user to choose which level maze to use (1-4). Error check input.
2. Dynamically allocate a 2D array of characters, the size of the array is read in from

   the first two values in the file.

3. Read in the rest of the file and store it in the array.
4. Allow the user to solve using DFS or BFS.
5. Create an empty stack/queue.
6. Search the array for the starting location.
7. Push the starting point onto the stack/queue.
8. Repeat the following Maze Solving Algorithm until the finish is found
   1. Pop a point from the stack/queue
   2. Test to see if this point is the finish

i. If it is, end the loop ii. Otherwise:

1. Mark the spot in the maze as evaluated (add a ‘.’ in the array). This will show the evaluated points when printed (note: this does not create a final path, this shows all points that were evaluated).
2. Check the spots in the maze that are neighboring the current location (up, down, left, right). If they are not a wall, and haven’t already been evaluated, then add those points to the stack/queue to be other locations to evaluate.

9. Print out the maze.
10. Repeat the program until the user quits.

Extra Credit Option – bonus 10 points (Note: this may only be done in addition to the above, and must be fully working) – Give the user the option of solving the maze themselves in addition to DFS and BFS. Display a menu so they may move up, down, left, right, or quit. Quitting will then solve the maze using DFS from where they left off (ie. not from the start).