import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; public class MazeSolver { static char[][] maze; static int m, n; // dimensions of the maze; row and col /* TODO: setMaze - sets up the board This method will take in a String, file, which is the path of the file we want to look at. Using BufferedReader and FileReader, write this method so that it sets the rows, m, and columns, n, to the first line of input. Then it fills the maze with the maze from the file. */ public static void setMaze(String file) throws IOException { // modify } /* TODO: isValid - checks if a position on the board has not been visited and is within bounds */ public static boolean isValid(int x, int y) { // modify return false; } /* TODO: solveMaze - recursive function which will traverse the maze and find whether it's solveable S -> G The input is the index that we want to check: x = row, y = column ------ Hint ------- Cell(i,j) -> if its a wall return false Cell(i,j) is G return true Otherwise, mark cell(i,j) as visited (maybe make it a wall) and return if you can find a way out from the top, bottom, left, or right */ public static boolean solveMaze(int x, int y) { // modify return false; } /* TODO: solve - sets the maze up, solves the board, print whether it can be solved or not, returns whether its solvable or not */ public static boolean solve(String file) throws IOException { // modify System.out.println("Maze can be solved: " + false); return false; } }

You will be writing a program to find if it is possible to find a way out of a maze. The maze is to be read from a text file, "maze.txt". The format of the text file is fixed: - The first line will contain the dimensions of the mxn array, which will be space separated. - This will be followed by m lines each of which contains n characters. - Each character can either be: - S denoting the starting point (which may be anywhere in the maze). - G to denoting the ending point (where you need to go to reach the end) . denoting the path you can take \# denoting wall (which you cannot traverse) As you can observe it is possible to reach the end: You are not required to find the path to the end. Only if it is solvable or not. Here are some helpful hints for you to think about: - If you are at a particular position, explore all possible paths. - But you must make sure you don't visit the same position again so mark it as visited (make it a wall?). - If you encounter ' G ' it is solvable. You are provided a skeleton code. Do not change any of the function headers. You are only allowed to modify the body of the functions marked with TODO. You are allowed to write helper methods as well. Here are some more examples for you to try out: Maze 1: 66 S.... \#\#\#.\# \#..... \#. \#\#\#\# ....G G Maze 2: 78 S\#\#.\#\#.\# \#. \#\#\#\#.\# \#.\#\#\#\#. \# \#. \#\#\#\# \#. \#.\#..\#.\# \#..G... * Maze 3: 1115 S\#\#\#\#\#\#\#\#\#\#\#\#\#\# \#\#\#\#\#\#\#\#..... \#\# ###.#######.## #===,. \#\#.\#\#\#.G\#\#\#\#.. ##.#########.# \#............ F Sample run for each: Maze 1: Goal has been reached! Maze 2: Goal has been reached! Maze 3: Goal could not be reached Please sure to read the TODO's descriptions on how the functions should operate. Also be sure to submit tests that fulfill our requirements as it is 20% of your assignment grade. Submit on Autograder -MazeSolver.java Submit on Canvas -MazeSolver.java -MazeSolverTest.java