In the tutorial code provided, there are classes called Maze and Rat that represent a rat moving through a maze. There is also a class called MazeTestProgram that allows you to test out a method called canFindCheeseIn(Maze m), which we wrote in class. Run the code to make sure that it works. Try to understand the method if you are not sure what it is doing. Add the following lines to the end of the MazeTestProgram code:

m = Maze.sampleMaze();

r.moveTo(1,1); m.display(1,1);

System.out.println("Free Spaces = " + r.freeSpaces(m));

m.display(1,1);

Write a recursive method in the Rat class called freeSpace(Maze m) that determines the number of unique spaces that the rat can move around in from its starting location (i.e., (1,1) in this case). Do not worry about unmarking the locations in the maze as being unvisited, simply leave them as being visited once the rat reaches that location. Note that the method will be similar in structure to the canFindCheeseInMaze() method but it must return an integer. The result for our test case should be 104. Make sure that your code works

MAZE:

public class Maze { public static byte EMPTY = 0; public static byte WALL = 1; public static byte CHEESE = 2; public static byte BREAD_CRUMB = -1; private int rows, columns; private byte[][] grid; // A constructor that makes a maze of the given size  public Maze(int r, int c) { rows = r; columns = c; grid = new byte[r][c]; } // A constructor that makes a maze with the given byte array  public Maze(byte[][] g) { rows = g.length; columns = g[0].length; grid = g; } // Return true if a wall is at the given location, otherwise false  public boolean wallAt(int r, int c) { return grid[r][c] == WALL; } // Return true if a cheese is at the given location, otherwise false  public boolean cheeseAt(int r, int c) { return grid[r][c] == CHEESE; } // Put a wall at the given location  public void placeWallAt(int r, int c) { grid[r][c] = WALL; } // Remove a wall from the given location  public void removeWallAt(int r, int c) { grid[r][c] = EMPTY; } // Put cheese at the given location  public void placeCheeseAt(int r, int c) { grid[r][c] = CHEESE; } // Remove a cheese from the given location  public void removeCheeseAt(int r, int c) { grid[r][c] = EMPTY; } // Mark the given location as visited  public void markVisited(int r, int c) { grid[r][c] = BREAD_CRUMB; } // Mark the given location as not having been visited  public void markUnVisited(int r, int c) { grid[r][c] = EMPTY; } // Return true of the location has been visited  public boolean hasBeenVisited(int r, int c) { return grid[r][c] == BREAD_CRUMB; } // Display the maze  public void display() { for(int r=0; rfor (int c = 0; cif (grid[r][c] == WALL) System.out.print("W"); else if (grid[r][c] == CHEESE) System.out.print("c"); else  System.out.print(" "); } System.out.println(); } } // Display the maze, the rat and the breadcrumbs  public void display(int ratRow, int ratCol) { for(int r=0; rfor (int c = 0; cif ((r == ratRow) && (c == ratCol)) System.out.print("r"); else if (grid[r][c] == WALL) System.out.print("W"); else if (grid[r][c] == CHEESE) System.out.print("c"); else if (grid[r][c] == BREAD_CRUMB) System.out.print("."); else  System.out.print(" "); } System.out.println(); } } // Return a sample maze corresponding to the one in the notes  public static Maze sampleMaze() { byte[][] grid = { {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,1}, {1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,1}, {1,0,1,0,0,0,1,1,1,0,0,1,0,0,0,1,0,0,1}, {1,0,1,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,1}, {1,0,1,0,1,0,1,1,1,0,0,0,0,0,0,0,0,0,1}, {1,0,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1}, {1,0,1,1,1,1,1,1,0,0,0,1,1,1,0,1,1,0,1}, {1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,0,1}, {1,1,1,0,1,0,1,0,0,1,0,1,0,0,0,1,0,0,1}, {1,0,1,0,1,1,1,1,1,1,0,1,1,0,1,1,0,0,1}, {1,0,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}; Maze m = new Maze(grid); m.placeCheeseAt(3,12); return m; } } 

RAT:

public class Rat { private int row, col; // Move the Rat to the given position  public void moveTo(int r, int c) { row = r; col = c; } public boolean canFindCheeseIn(Maze m) { //m.display(row, col);  // Return true if there is cheese at the rat's (row,col) in the maze  if (m.cheeseAt(row, col)) return true; // Return false if there is a wall at the rat's (row,col) in the maze  if (m.wallAt(row, col) || m.hasBeenVisited(row, col)) return false; // Mark this location as having been visited  m.markVisited(row, col); // Move up in the maze and recursively check  moveTo(row-1, col); if (canFindCheeseIn(m)) { moveTo(row+1, col); // Move back down before marking  m.markUnVisited(row, col); // Unmark the visited location  return true; } moveTo(row+1, col); // Move back down before marking   // Move below in the maze and recursively check  moveTo(row+1, col); if (canFindCheeseIn(m)) { moveTo(row-1, col); // Move back up before marking  m.markUnVisited(row, col); // Unmark the visited location  return true; } moveTo(row-1, col); // Move back up before marking   // Move left in the maze and recursively check  moveTo(row, col-1); if (canFindCheeseIn(m)) { moveTo(row, col+1); // Move back right before marking  m.markUnVisited(row, col); // Unmark the visited location  return true; } moveTo(row, col+1); // Move back right before marking   // Move right in the maze and recursively check  moveTo(row, col+1); if (canFindCheeseIn(m)) { moveTo(row, col-1); // Move back left before marking  m.markUnVisited(row, col); // Unmark the visited location  return true; } moveTo(row, col-1); // Move back left before marking   // We tried all directions and did not find the cheese, so quit  return false; } } 

MAZETESTPROGRAM:

public class MazeTestProgram { public static void main(String[] args) { Maze m = Maze.sampleMaze(); Rat r = new Rat(); r.moveTo(1,1); m.display(1,1); System.out.println("Can find cheese ... " + r.canFindCheeseIn(m)); m = Maze.sampleMaze(); m.placeCheeseAt(13,13); r.moveTo(1,1); m.display(1,1); System.out.println("Can find cheese ... " + r.canFindCheeseIn(m)); m = Maze.sampleMaze(); m.placeCheeseAt(6,12); r.moveTo(1,1); m.display(1,1); System.out.println("Can find cheese ... " + r.canFindCheeseIn(m)); m = Maze.sampleMaze(); m.placeCheeseAt(13,1); r.moveTo(1,1); m.display(1,1); System.out.println("Can find cheese ... " + r.canFindCheeseIn(m)); m = Maze.sampleMaze(); m.placeCheeseAt(13,3); r.moveTo(1,1); m.display(1,1); System.out.println("Can find cheese ... " + r.canFindCheeseIn(m)); } }