Susie Queue and Hay Stack are good friends, but they are currently in a difficult situation. They are trapped in an underground cave. They must either find a way out of the cave, or determine that there is no exit so they can radio for help. They both think they should keep a list of possible paths from their current location in order to find their way out. However, they disagree about the exact approach they should use to search for the exit. Hay thinks they should always try the most recently seen path first, but Susie thinks they should try the paths seen earliest first. They are unable to settle the dispute, so they decide to go their own ways and meet up at the exit.
For this assignment option, develop an object-oriented C++ program that finds a path through a maze using two different algorithms, one using a static stack and one using a dynamic queue. The program must input the maze from a text file, output the maze to a text file, and then output both paths, along with the number of moves made in each path. Your program must consist of the static Stack class and the dynamic Queue class from the textbook, a Square class, and a Maze class that you create, and a file named StackQueue.cpp that contains the main() method. When designing and implementing the program, apply good software engineering principles. Create a makefile for the program. Start the analysis and design process by drawing a complete UML class diagram for the program that includes all the classes that are contained in the makefile. After you have completed the program, update the UML class diagram to reflect the completed implementation.
The files for the Queue class and the Stack class from the textbook (Queue.h, Queue.cpp, QueueException.h, Stack.h, Stack.cpp, and StackException.h) are provided in a zipped folder on the course web site, along with two sample input files you can use to test your program. When the program ends, all stacks and queues must be empty.
The Square class is used to store one square (location) in the maze. The class must store the following attributes:
1) Row number for the square
2) Column number for the square
3) Direction followed to reach the square
You may include other attributes, as well. The Square class must provide the following methods:
1) Constructor
2) Accessors and mutators for each attribute
3) Method to output the data for this square, where the output file stream is passed as a parameter.
You may include other methods, if needed.
The Maze class is used to store the maze and find two paths through the maze, one path that is found using a stack and one path that is found using a queue. The class must store the following attributes:
1) Original maze input from the input file. The maze is a two dimensional array of characters containing 12 rows and 12 columns. Be sure to use a constant for the maze size.
2) Stack object that stores Square objects that are reachable from the current square
3) Queue object that stores Square objects that are reachable from the current square
4) Output file stream used to save all the output data
You may include other attributes, as well. The Maze class must provide the following methods:
1) Constructor
2) Method to input the data for the maze from a text file, the name of which is entered by the user. The file for each maze contains 12 lines of text, each of which contains 12 characters. This method must also obtain the name of the output file from the user and open the output file. Valid characters in the input file are shown in the table below.
Character
Meaning
S
Start; where the search for a path to the exit begins.
E
Exit; where the search for a path to the exit ends.
Space
You can move into a square containing a space.
#
Wall; you cannot move into a square containing a wall.
3) Method to output the original maze to the output file, with the rows and columns numbered from 0 to 11. The output must look like the following:
The maze contains the following:
1 1
0 1 2 3 4 5 6 7 8 9 0 1
-------------------------------------------------
0 | S | | | | | | # | | | | | |
-------------------------------------------------
1 | # | # | | # | # | # | # | # | # | # | | # |
-------------------------------------------------
2 | | # | | | | | | | | | | # |
-------------------------------------------------
3 | | # | | # | # | | | # | # | # | | # |
-------------------------------------------------
4 | | | | # | | | | | | # | | # |
-------------------------------------------------
5 | | # | # | # | # | # | | # | | # | | # |
-------------------------------------------------
6 | | # | # | # | # | # | | # | | # | | # |
-------------------------------------------------
7 | | # | # | # | # | # | | # | | # | | # |
-------------------------------------------------
8 | | # | # | # | # | # | | # | | # | | # |
-------------------------------------------------
9 | | # | # | # | # | # | | # | | # | | # |
-------------------------------------------------
10 | | # | # | # | # | # | | # | | # | | # |
-------------------------------------------------
11 | | | | | | | | # | | # | | E |
-------------------------------------------------
4) Method to find a path through the maze, searching for the exit, using Hay Stack's approach to store possible paths. Do NOT use recursion to find the path through the maze. The exit is in the square that contains the letter 'E' for Exit. Start your search at square 0, 0 in the maze (row 0, column 0), which contains the letter 'S' for Start. You may move horizontally or vertically in the maze, BUT NOT DIAGONALLY. This means that you can move up, down, left, or right. Begin by pushing the Start square onto the stack. Here is the algorithm to find the path using a stack:
while a good path has not been found and the stack is not empty, do the following
a. pop a square from the stack; this becomes the current square
b. store the direction from the current square into that square's location in the working maze so you will be able to output the path later. (Note: you will need to use the original maze again when searching for the exit using the queue, so do not overwrite the original maze.)
c. check all four directions (as long as you still have not found the exit), first to see if it is the exit. If it is the exit, set good path variable to true and call the method to print all the moves in the path. If it is not the exit, check to see if you can move there from the current square (i.e., the square contains a space). If so, store the direction you followed to reach this square (Up, Down, Left, or Right) and push the square onto the stack. (Note: be sure to check for a full stack before pushing.)
5) Method to find a path through the maze, searching for the exit, using Susie Queue's approach to store possible paths. Do NOT use recursion to find the path through the maze. Use the same algorithm you used for the stack, but substitute the queue. Note that you will not need to check for a full queue, since the queue implementation is dynamic.
6) Method to output the moves through the maze to the output file. Create an empty stack to store the moves and push the square containing the Exit onto it. Using the direction followed to reach the Exit square, back up to the previous square and push that square onto the moves stack. Using the direction stored in the maze for the previous square, back up into its previous square and push that square onto the moves stack. Keep backing up in this way into the previous square, pushing each square onto the stack, until you reach the Start square. Count the number of moves in the path while you are pushing them onto the stack. Then output the number of moves made in the complete path, and output all the moves in the path by popping each square off the moves stack and calling the method in the Square class to output the row and column for that square. The user must be able to easily trace the exact path followed from the Start to the Exit.
7) Method to close the output file after all the output has been produced.
You may include other methods, if needed.
The StackQueue.cpp file must contain a main() method that creates a Maze object and calls appropriate methods to:
1) call the description() method (see below),
2) input the maze from the input file,
3) output a picture of the maze to the output file,
4) find and output two paths through the maze, one using a stack and one using a queue, and
5) close the output file.
This file must also contain a method named description() that is called by the main() method and provides a detailed explanation for the user about what the program is doing and how it works. The audience for this method consists of non-technical users that have no information at all about the assignment.