********THIS IS THE QUESTION***********

For the maze path found in Figure 5.19, explain why cells (3, 4), (2, 5), (3, 5), and (4, 5) were never visited and why cells (5, 1) and (3, 0) through (9, 0) were visited and rejected. Show the activation frames for the first 10 recursive calls in solving the maze. Class Maze

**********DETAILS ARE BELOW*************

Class Maze import java.awt.*; import static GridColors.*; /** Class that solves maze problems with backtracking. */ public class Maze { /** The maze */ private TwoDimGrid maze; public Maze(TwoDimGrid m) { maze = m; } /** Wrapper method. */ public boolean findMazePath() { return findMazePath(0, 0); // (0, 0) is the start point. } /** Attempts to find a path through point (x, y). pre: Possible path cells are in BACKGROUND color; barrier cells are in ABNORMAL color. post: If a path is found, all cells on it are set to the PATH color; all cells that were visited but are not on the path are in the TEMPORARY color. @param x The x-coordinate of current point @param y The y-coordinate of current point @return If a path through (x, y) is found, true; otherwise, false */ public boolean findMazePath(int x, int y) { if (x = maze.getNCols() || y >= maze.getNRows()) return false; // Cell is out of bounds. else if (!maze.getColor(x, y).equals(BACKGROUND)) return false; // Cell is on barrier or dead end. else if (x == maze.getNCols()  1 && y == maze.getNRows()  1) { maze.recolor(x, y, PATH); // Cell is on path return true; // and is maze exit. } else { // Recursive case. // Attempt to find a path from each neighbor. // Tentatively mark cell as on path.  maze.recolor(x, y, PATH);  if (findMazePath(x  1, y)  || findMazePath(x + 1, y)  || findMazePath(x, y  1)  || findMazePath(x, y + 1 ) ) {  return true;  } else {  maze.recolor(x, y, TEMPORARY); // Dead end.  return false;  } } } } 

The Effect of Marking a Cell as Visited

If a path can't be found from a neighbor of the current cell to the maze exit, the current cell is considered a dead end and is recolored to the temporary color. You may be wondering whether the program would still work if we just recolored it to the background color. The answer is yes. In this case, cells that turned out to be dead ends or cells that were not visited would be in the background color after the program terminated. This would not affect the ability of the algorithm to find a path or to determine that none exists; however, it would affect the algorithm's efficiency. After backtracking, the method could try to place on the path a cell that had been found to be a dead end. The cell would be classified once again as a dead end. Marking it as a dead end (color TEMPORARY) the first time prevents this from happening.

To demonstrate the efficiency of this approach, we tested the program on a maze with four rows and six columns that had a single barrier cell at the maze exit. When we recolored each dead end cell in the TEMPORARY color, it took 93 recursive calls to findMazePath to determine that a path did not exist. When we recolored each tested cell in the BACKGROUND color, it took 177,313 recursive calls to determine that a path did not exist.

Testing

We will use class TwoDimGrid and class MazeTest (from the textbook Web site) to test the maze. The MazeTest class is very similar to BlobTest. The main method prompts for the grid dimensions and creates a new TwoDimGrid object with those dimensions. The class constructor builds the graphical user interface (GUI) for the maze solver, including the button panel, and registers a listener for each button. When the SOLVE button is clicked, method MazeTest.actionPerformed calls findMazePath and displays its result. Figure 5.18 shows the GUI before the SOLVE button is clicked (barrier cells are in light gray, and other cells are in dark gray), and Figure 5.19 shows it after the SOLVE button is clicked and the final path is displayed. In Figure 5.19, the barrier cells are in light gray (ABNORMAL color), the cells on the final path are in white (PATH color), and the cells that were visited but then rejected (not on the path) are in black (TEMPORARY color).

FIGURE 5.18 Maze as Grid of Buttons before SOLVE Is Clicked

FIGURE 5.19 Maze as Grid of Buttons after SOLVE Is Clicked

You should test this with a variety of mazes, some that can be solved and some that can't (no path exists). You should also try a maze that has no barrier cells and one that has a single barrier cell at the exit point. In the latter case, no path exists