[Solved] CSCI3110 Project 5: Find Your Way Out

File(s) to be submitted: proj5.cpp, maze.h, maze.cpp, makefileObjectives: 1) Use recursion; 2) Understand and apply backtracking to solve a problem.Project description:Write a C++ program that, given a starting point, finds its way out of a maze, using recursion. The mazes map will beread from a file at the start of the program. Your code must work for all legal mazes. The maze is a rectangular gridrepresented as a 2D standard C++ array, and the exit (if there is one) is on an outer row or column of the play area (nonred cells below). The program should run until the exit to the maze is found or until it determines that there is no exit(after exploring all traversable/navigable cells). Exploration of the maze is done by recursively invoking a function andmarking the cells visited with a special character (an electronic bread crumb to keep from reprocessing explored cells).The legal moves are to cells adjacent to the current cell, but not diagonal to it. The order in which adjacent cells must beexplored is given below. The maze should be solved through recursive calls and backtracking, and not by looking ahead(you do not have the ability to look into neighboring cells before moving you simply move and rely on backtracking ifits a bad move). If the specially marked exit cell is encountered the game should print a message that the exit wasfound. Otherwise, after exploring the whole maze, a message is output stating that there is no exit.X X X X X X X X X XX * * * O X X X O XX X X O O O O O O XX O O O X X X O E XX O X O O O O O X XX O O O O O X X X XX X O X O O O O O XX X O X O X O X O XX O O X O O O X O XX X X X X X X X X XNW ESAt left is an instance of a maze. Note the attributes of a legal maze: Cells are referred to as row #, column #. Row numbers increasedownward, and column numbers increase to the right. The upper left cell of the play area, (cell 1,1) cannot be the exit, andmust always be a traversable cell and may not be boxed in by walls onall sides This is the players starting point. X marks non-traversable cells The cells in red are not part of the maze map read from the file,but must be constructed around it and represented in the array.They mark the boundary of the maze, and are represented as nottraversable. The maze will always have two more columns andtwo more rows than the play area read from the file (the maze atleft has an 88 play area and is shown in a 1010 array). Blue squares are walls and are also non-traversable. O cells (green) are traversable cells not yet visited. Traversable cells (andthe exit) must be reachable from any other traversable cell. * (yellow) shows traversable cells that have been previously visited. E marks the exit (outlined gray cell) If there is one, it must be on one ofthe outer rows or columns of the play area, and must be reachable fromany traversable cells in the maze (it cant be contained within walls). You must explore the maze in the following order: North, East, South, andthen West. Assuming you begin at the home plate cell () shown at left,you must explore in this order: N, E, S, W.Requirements:1. Your program must be split into 3 files. There will be a class (with separate interface and implementation files), and adriver file. The requirements for these are specified below:a) The Maze class This class represents a maze Files must be named maze.h and maze.cpp Class must be named Maze The interface (header file) is provided.i. You should implement the interface file in a .cpp implementation fileii. All data members must be of the type and size specified in the header fileiii. All member functions in the interface file must be implemented as declared However you haveflexibility in how you choose to implement the body of functions, including choice of local variables. The constructor will accept a file object argument and will read the file and construct the maze.The file contains a rectangular maze no larger than 8 cells by 8 cells your code must be able tohandle all mazes from those having a minimum of two rows (21) or two columns(12) up to themaximum 88. The first line in the file has the dimensions of the maze (# of rows followed by #of columns, separated by a space). An example maze file (4 rows by 4 columns) is shown below.Note: There are no spaces between cell legend symbols in the input file. 4 4 OOOX XOXX XOOX XXEO The Print() function outputs the mazes current state (using the legend above, including cellsvisited thus far). It must only be output in unvisited traversable cells. See sample output. The FindExit() function is a recursive function that explores the maze. It has two int parametersindicating the players current row and column (in that order), and a bool reference variable thatrepresents whether or not the exit has been found. The exploration of the maze will alwaysbegin at row 1, column 1 (which must thus be a traversable grid cell). This function must rely onrecursion to explore the maze and to backtrack. It is a void function and you MAY NOT use areturn or break statement in it. Write the code so that it flows naturally. You should considerthe 4 questions to ask when planning to use recursive algorithms, as you design your approach: How are smaller instances of the problem defined? How does each recursive call make the problem instance smaller? What condition(s) can serve as the base case(s)? Will the smaller instances of the problem reach the base case(s)?b) A driver, or client, file Must be named proj5.cpp Must declare the file object containing the maze map. The maze is read from a file named maze.txt, whichis contained in the same folder as the source files. Must instantiate maze Must invoke the FindExit function, beginning at cell 1,1. Outputs an appropriate message Found exit! or No exit!, based on the outcome of maze exploration.

2. Sample output:a) This output show possible program executions with the player starting at cell 1,1 The Exit case is from the 44maze file shown above. The No Exit case results from converting the E in the maze file to an O.Case with Exit Case with No Exit3. Test your program Use different maze configurations, with and without exits.4. Code comments Add the following comments to your code: A section at the top of the source file(s) with the following identifying information:Your NameCSCI 3110-00X (your section #)Project #XDue: mm/dd/yy Below your name add comments in each file that give an overview of the program or class. Place a one or two-line comment above each function that summarizes the workings of the function.5. RubricRequirement Points OffMaze ClassClass name -5Include guards -3Constructor number, types, and order of parameters -5 (per item)Constructor file correctly read and maze correctly built (including outer boundary) -15FindExit correct function signature -5FindExit correctly handles wall cells -5FindExit correctly handles previously visited cells -5FindExit avoids look-ahead -5FindExit explores maze in specified order -10FindExit utilizes recursion and backtracking to solve the maze -15FindExit invokes Print function only in appropriate cells -5FindExit correctly terminates exploration (does not overexplore the maze) -10FindExit correctly sets/uses bool reference variable -5Print correct output -10Driver/Clientmain input filename -5main correctly opens input file -5main correctly instantiates Maze object -10main correctly invokes the mazes FindExit function -5main correctly outputs the outcome of exploring the maze -5general Does not compile (on ranger using Linux g++ compiler, and the provided makefile) -25general Runtime crash -35general Other TBD