Solving Mazes Note: There are no restrictions for loops, arrays, and global variables for this program. Create a program that will read from a file a maze an array and then find a path through the maze. When the program has found a path through the maze, it should print to the screen the path that it found. Your path can only be up, down, left or right. Since there are solutions on the Internet for solving a maze, you will only be allowed to solve the maze by implementing the recursive algorithm given to you on the HUB. b. Once the maze the maze code is able to solve the maze, implement a visited two- dimensional array with the same dimensions as the maze. The purpose of the visited array will be to track locations in the maze, which has been visited and not visited that spot again. Initially set all locations in the visited array to 0, then as a path is taken, change the value to 1. Adjust your code to not visit a location that you have already bee. The format of the file is that the first line will contain information about the numbers of rows and the number of columns for the maze. Key to the maze characters: wall empty floor e entrance (starting position) exit (ending position) step that your program takes . . . .mark your trail as you go. . . .and don't forget to erase your marks if you need to go back Sample file#1 7, 11 8 . . . 8. 8 . . . 8 8. 8 .8. 8. 898 8. 8 . . ..... 8 8. 8 . .. . . 8. 8 Sample file#2 8, 10 &. . . . . ...8 $8. 8. 8. $88 8 . . .. 8 . ..8 8. 8 . 8 . 88 .8 e . $ . . . .8.8 $48. . 848.X Sample file#3 11, 26 S . . . . . . . . . . . . . .. . . ..8 8 8 8 . . . . .. $8. $8 . 838.....$88. 8 $48. 88. $8.8..88.. 838...8. 8 e. . . $8. $8. 8. 88 88. 838. 848. 8 $88.8.. $8.8.8 ....8... $8. .8 $48. 89838. 898.189838. ...88 B..... 848. 898 .... 838. 8.898 $. 858. 838..... 18. 98.. . ...x Sample file#4 15, 28 B.. . 8.... . 8.. .. . . . .$ $. . . . . .8.. .. .$48. . . .4 3..$8.. $8 ...... 8. . . . ..8. .. .e S.. .... $8 . ... 8. . .8. .. . .. . 8.8 ..8988..... 8.... 8.... 898. . 8 S. .... 68.... 86... 9868... .838 B..9868388....8.8.8... .. . . ." S. . . . . . . . . . . . . . . 6. . . . . . . . .. $8898....... 8...8..8. . 1898 8 8 $..... B.8... 888 ....8... . . .. $88 .... 8 .... 8 .... 868 .... 88.8 $8. .. . 8. 8. 8... 8 ..... $88 . . . .Algorithm to find a recursive path through a maze \"Read the file and store the maze in a two dimensional array of characters \"Determine the start and end positions {fnd the path through the maze Note: This solution would be coded in a Boolean method called findPath, where x and y are the current row and column in the maze. 1. Check if x,v is within the mazelboundaries}, if not return false. The location is outside the maze. 2. Check If x,y is the goal, return true. The exit location is found. 3. Check if maze at location x,y is an open position, if not return false. Location could be a wall, or other character that is not able to be moved to. 13. Mark the maze location as part of the solution path (choose a character to mark the path ie '+' 5. Recursion a. Try' North of the current location, return true b. Trv South of the current location, return true c. Trv West of the current location, return true d. Try East of the current location, return true 6. BACKTRACK: unmark the maze at x, v, as it is not part of the solution 7. Return false Note: A sample of the recursion iflfindPath[x,v-1}==true}return true; forth Backtracking makes use of the unwinding of the recursion and is placed after the recursive calls. Backtracking will undo the path until another path can be taken. In the above algorithm, one line is used to code the backtracking. Set the maze at the current x, v value to