In this project you will create an automatic maze solver. Given a maze, a starting point, and an ending point, your program will print out the successful path if it exists, otherwise it will print out all of the parts of the maze that can be reached from a starting point.You can think of this program as a piece of code that tests a video game in which a character (let's say Mario) must move from a specified starting point (let's say Mario's plumbing business office) to a specified ending point (let's say the Princess' castle). Since the video game was developed by different people, you are making sure that it is possible for Mario to save the princess by moving through the game (you don't want to ship a game that no one can win). Input: Input to the program will be a file (for instance, called “maze.txt”). The first line of the file is the width of the maze. The second line of the file is the height of the maze. The lines that follow depict the maze. Each character in each line has a special meaning: • M is Mario's plumbing business location (starting point) • P the the Princess' castle (exit point) • (blank space) is a place Mario can visit • +, |, and - are walls (places Mario can't visit) Two sample input files can be found as follows: 1. Mario can save the Princess: mazeSmall.txt 2. Mario cannot save the Princess: mazeFail.txt Setup: Your program should model the maze and model Mario's progress through the maze. One mandatory class is MazeSolver, but you may use more classes if you choose (such as a simple position class for Mario). The following member components will be necessary: • Data: Mario's current position in the maze (starting point at the plumbing business) • Data: Width and height of maze • Data: The maze itself. This will be a 2D data structure (such as a 2D array or 2D vector) • Methods (recursive): Move Mario north, south, east, or west • Method(s): Mark a specified space with one of the possible states • Method: Display (print) the maze • Method: Search for a path*Note that all of the maze setup and processing will be performed in your class(es). The client file in this assignment should simply create a MazeSolver object which solves a given maze from a text file. A full example client file called L5_Main.cpp is included on Canvas, which is the only client code needed in this assignment. Make sure you include your identifying information at the top of the file. If you make any modifications to the file, note them and justify why. Setup Procedure: o You will need to provide an initialization function (either in an overloaded constructor or called from a separate function) which reads in a text file argument from the client (e.g. “maze.txt”) and stores the maze information from the file. o Store the maze in a two-dimensional rectangular arrangement of locations (such as a 2D array or 2D vector). The northwest corner will be location (0, 0) and the southeast corner will belocation (h-1, w-1), where h and w are the height and width, respectively (if it helps, think of how pixels are arranged in an image). o To simplify your maze and to get practice with manipulating it, try changing every blocked state (+, |, and -) to simply a + (this is a requirement). o As you are storing the file, if you encounter a location labeled M, store the location (row, column position, for example) as Mario’s location. o Implement a displayMaze function to display the current state of the maze. Make sure you are able to read in, store, and print the maze before moving on. Processing: Each place in the maze should be now symbolically marked as: • Mario M (Mario’s current location) • clear ((black space) Mario can visit it), • blocked + (if Mario can't visit it), or • princess P (the goal, or exit, point). As Mario moves through the maze, he will re-mark the clear spaces as either... • maybe ? (might lead to the Princess) or • no * (definitely does not lead to the Princess). Processing Procedure: To help simplify the assignment, here is some information to help you implement the code that allows Mario to try all of the possible paths to get to the Princess. With Mario starting at his business and the Princess being somewhere else in the maze, follow these steps to searchForPath: 1. Try moving north by calling the goNorth function. 2. If going north resulted in rescuing the princess, stop. Otherwise, trying moving east by calling the goEast function. 3. If going east resulted in rescuing the princess, stop. Otherwise, trying moving south by calling the goSouth function. 4. If going south resulted in rescuing the princess, stop. Otherwise, trying moving west by calling the goWest function. 5. If going west resulted in rescuing the princess, stop. Otherwise, stop: Mario cannot reach the Princess. goNorth tries all paths that start to the north of the current place by executing the following logic. 1. First make sure that there is an open space to the north (for example, Mario might currently be as far north as possible, so he can't move north again). If there is no open space to the north, stop. 2. If the space to the north is the Princess castle, also stop. 3. Otherwise, if the space to the north is clear, then Mario moves there and re-marks the space as maybe. 4. Now try all paths from this new place to the Princess... 1. Try moving north by calling the goNorth function. 2. If going north resulted in finding the princess, stop. Otherwise, trying moving east by calling the goEast function. 3. If going east resulted in finding the princess, stop. Otherwise, trying moving west by calling the goWest function.4. If going west resulted in finding the princess, stop. Otherwise, there is no path from here to the Princess, so re-mark the space as no and move back to the south.If we were to write the description in pseudo code, it would look like this. goNorth(&rescued) { if Maze north space exists { if Maze north space is Princess { Set rescued to true } else if Maze north space is clear { Move Mario to north space Mark space as maybe goNorth(rescued) if rescued is false { goEast(rescued) } if rescued is false { goWest(rescued) } if rescued is false { Mark space as no Move Mario to south space } } } else { Set rescued to false } } Notice the recursive nature of this problem: goNorth will continue to call goNorth until Mario cannot move into a north space (or finds the princess). The other three functions are similar. 1. In goSouth, check if the space to the south exists. If the south space is the princess, set rescued to true. If the south space is clear, move there and mark it as maybe. Try spaces to the south, east, and west and stop if any one of them results in finding the Princess. Otherwise mark the space as no and move back north. 2. In goEast, check for a clear east space, move there, mark as maybe, try spaces east, north, and south, and mark as no and move back west if you do not find the princess. 3. In goWest, check for a clear west space, move there, mark as maybe, try spaces west, north, and south, and mark as no and move back east if you do not find the princess. I have given you most of the pieces that you need to implement a solution to the maze path-finding problem. To summarize, your job is as follows.