Remembering Where We Have Been

We can remember where we have been by marking cells as visited when we search from them. We could do this in the maze array itself, but it is better to keep the original maze unchanged and use a separate auxiliary data structure to track the visited cells.

Let’s define visited as a 2D boolean array with the same dimensions as the maze:

boolean[][] visited = new boolean[maze.length][maze[0].length];

A cell is visited when visited[row][col] is true. By “visited”, I mean the search has already started searching from that cell. Once a cell has been visited, there is no reason to search from it again; that would only repeat work we already started.

Here is the updated version of the recursive solution:

public static boolean hasPath(char[][] maze) {
  boolean[][] visited = new boolean[maze.length][maze[0].length];
  return search(maze, visited, 0, 0);
}

private static boolean search(
    char[][] maze, boolean[][] visited, int row, int col) {

  if (!isOpen(maze, row, col)) {
    return false;
  }
  if (visited[row][col]) {
    return false;
  }
  if (isExit(maze, row, col)) {
    return true;
  }

  visited[row][col] = true;

  return search(maze, visited, row, col + 1)  // right
      || search(maze, visited, row + 1, col)  // down
      || search(maze, visited, row, col - 1)  // left
      || search(maze, visited, row - 1, col);  // up
}

There are a few things to notice here:

• We declare the visited array in the hasPath method and pass it to the search method. If we were to declare it inside the search method, it would be reset on each recursive call.
• We check if a cell is already visited as part of the base cases and stop the search if it is. Returning false here does not mean the search failed. It means the search has already started from this cell.
• We mark the current cell as visited before making recursive calls. We do not need to mark a cell that is a wall or the exit as visited, since the base cases for walls and the exit return before the marking step.

The pictures below show the maze on the left and the visited array on the right. The cell being searched is in brackets, and x marks a cell whose entry in visited is true:

┌───┬───┬───┐       ┌───┬───┬───┐
│[S]│   │ █ │       │ x │   │   │
├───┼───┼───┤       ├───┼───┼───┤
│   │ █ │ E │       │   │   │   │
└───┴───┴───┘       └───┴───┴───┘
    maze               visited

If a later recursive call is on a cell that is already visited, the visited check stops it. After the search moves right and finds walls to the right and below, it tries to step back left onto the start. But the start is already visited, so that call returns false right away instead of searching from the start again:

┌───┬───┬───┐       ┌───┬───┬───┐
│[S]│   │ █ │       │ x │ x │   │
├───┼───┼───┤       ├───┼───┼───┤
│   │ █ │ E │       │   │   │   │
└───┴───┴───┘       └───┴───┴───┘
    maze               visited

Edge Cases

Now that the search tracks visited cells, let’s go back to the edge cases we named when we stated the problem and see how this version handles them:

• If the start cell is a wall, the first call fails the isOpen check and returns false.
• If the exit cell is a wall, a call on the exit fails the isOpen check before it gets to the isExit check. So no call ever returns true, and the search returns false.
• If the maze has one open cell, the first call passes the isOpen and visited checks, and then isExit returns true.
• The search does not keep revisiting the same cells forever. The visited check stops it, as the pictures above show.