For this assignment, you will use recursion to solve mazes!

Each maze will be specified by a text file containing 2 integers that specify number of rows and number of columns on the first line, then # marks for barriers, one S for the starting position, and one G for the goal position. As the maze is solved, your code will leave breadcrumbs, indicated by . characters.

The sequence of moves, with U, R, D, and L indicating Up, Right, Down, and Left moves, and G indicating the Goal is reached, is

LLUUUUUUURRRRRRDDDDDLUUUG 

Notice that this is not the shortest path to the goal. The search method we will be implementing is a "depth-first search", and is not likely to find the shortest path.

For this assignment, you will code a single class called Maze that implements the IMaze interface seen below:

public interface IMaze { public char[][] readFile(String filename); /* Precondition - filename set to file containing map of the maze. * Postcondition - two dimensional char array holding a map of the maze * Postcondition - returns null if file not found */ public int[] findStart(char[][] maze); /* Precondition - maze array initialized to a valid maze * Postcondition - array containing row, column of location of S * returned. Ex. if S is in maze[1][2]. the return * array is {1, 2} * Postcondition - returns null if no S found */ public String findPath(char[][] maze, int[]startPosition); /* Precondition - maze array initialize to a valid maze * Precondition - StartPosition contains row, column of location of S * Ex. if S is in maze[1][2], the startPosition * array is {1, 2} * Postcondition - returns a String composed of the appropriate * characters from 'U', 'R', 'D', 'L', and the final 'G', * indicating the solution path. * Postcondition - successful path marked with '.' characters in maze * array from 'S' to the final 'G', indicating the * solution path. */ public String printMaze(char[][] maze); /* * Postcondition - returns a String representation of the map character array * (complete with end of line characters). */ }

The main method of Maze will get the filename from the command line, call the methods described in the interface to solve the maze, and print the resulting map and the solution path.

The findPath method described in the interface will call a private helper method called recPath. The signature of recPath is:

 private String recPath(char[][] maze, int r, int c); /* * Precondition - maze array initialized to a valid maze * Postcondition - returns the path from the location r,c to the goal * Postcondition - '.' set from location r,c in the maze to the goal * Requirement - Implemented as a recursive method that finds a path * from position (row,col) to the goal position, * marked by 'G' */ 

recPath must implement a recursive algorithm for finding a path to the goal from the position (row,col) given as an argument.

Base cases:

If position (row,col) is outside of the maze, return "".

If the character at position (row,col) in the map is a '#' or '.', return "".

If the character at position (row,col) in the map is a 'G', return "G". You found the goal!!

Recursive cases:

Mark the map at position (row,col) with a '.'

Try to find a path to the goal from position (row-1,col). If found, add 'U' to the returned path and return it.

Try to find a path to the goal from position (row,col+1). If found, add 'R' to the returned path and return it.

Try to find a path to the goal from position (row+1,col). If found, add 'D' to the returned path and return it.

Try to find a path to the goal from position (row,col-1). If found, add 'L' to the returned path and return it.

If you reach here, no path to the goal from (row,col) was found. Remove the mark '.' at map position (row,col), by replacing with a blank, and return "".

To solve the above maze, make a file with the following contents.

Say it is saved in a file named maze1. The result of compiling and running your Maze class must be exactly as shown below.

10 10 th th th th th th th th th th th th th th th th G th th th th th th th th th th th th th th th th 10 10 th th th th th th th th th th th th th th th th G th th th th th th th th th th th th th th th th