Solution: Measuring Distance with a Queue

We need to modify the queue-based search to keep track of the distance from the start to each cell.

Let’s add a distance 2D array that starts with -1 everywhere, meaning “not visited yet.” So we can use this array to record each cell’s distance and to track which cells have been visited.

public static int distanceToExit(char[][] maze) {
  if (!isOpen(maze, 0, 0)) {
    return -1;
  }

  int rows = maze.length;
  int cols = maze[0].length;
  int[][] distance = new int[rows][cols];
  for (int row = 0; row < rows; row++) {
    for (int col = 0; col < cols; col++) {
      distance[row][col] = -1;
    }
  }

  Queue<Position> toExplore = new LinkedQueue<>();
  toExplore.enqueue(new Position(0, 0));
  distance[0][0] = 0;

  int[] rowChange = {0, 1, 0, -1};
  int[] colChange = {1, 0, -1, 0};

  while (!toExplore.isEmpty()) {
    Position current = toExplore.front();
    toExplore.dequeue();

    if (isExit(maze, current.row, current.col)) {
      return distance[current.row][current.col];
    }

    for (int i = 0; i < rowChange.length; i++) {
      int nextRow = current.row + rowChange[i];
      int nextCol = current.col + colChange[i];
      if (isOpen(maze, nextRow, nextCol)
          && distance[nextRow][nextCol] == -1) {
        distance[nextRow][nextCol] =
            distance[current.row][current.col] + 1;
        toExplore.enqueue(new Position(nextRow, nextCol));
      }
    }
  }

  return -1;
}

The isOpen and isExit helpers and the Position class are the same ones used in the chapter.

Let’s trace the method on the following maze. The search begins with the start cell recorded at distance 0, and it is the only cell in the queue:

┌───┬───┬───┐       ┌────┬────┬────┐
│ S │   │   │       │  0 │ -1 │ -1 │
├───┼───┼───┤       ├────┼────┼────┤
│ █ │ █ │   │       │ -1 │ -1 │ -1 │
├───┼───┼───┤       ├────┼────┼────┤
│   │   │ E │       │ -1 │ -1 │ -1 │
└───┴───┴───┘       └────┴────┴────┘
    maze                distance

┌────────┐
│ (0, 0) │
└────────┘
     ▲
front, back

Each time a cell is dequeued, every open neighbor not visited yet gets a distance one more than the cell’s own. After (0, 1) is dequeued, every cell in the top row has a distance, and the cell at the front of the queue is (0, 2), recorded at distance 2:

┌───┬───┬───┐       ┌────┬────┬────┐
│ S │[ ]│   │       │  0 │  1 │  2 │
├───┼───┼───┤       ├────┼────┼────┤
│ █ │ █ │   │       │ -1 │ -1 │ -1 │
├───┼───┼───┤       ├────┼────┼────┤
│   │   │ E │       │ -1 │ -1 │ -1 │
└───┴───┴───┘       └────┴────┴────┘
    maze                distance

┌────────┐
│ (0, 2) │
└────────┘
     ▲
front, back

After (1, 2) is dequeued, the exit at (2, 2) is recorded with distance 4, and it is the cell now at the front of the queue:

┌───┬───┬───┐       ┌────┬────┬────┐
│ S │   │   │       │  0 │  1 │  2 │
├───┼───┼───┤       ├────┼────┼────┤
│ █ │ █ │[ ]│       │ -1 │ -1 │  3 │
├───┼───┼───┤       ├────┼────┼────┤
│   │   │ E │       │ -1 │ -1 │  4 │
└───┴───┴───┘       └────┴────┴────┘
    maze                distance

┌────────┐
│ (2, 2) │
└────────┘
     ▲
front, back

When (2, 2) is dequeued, it is the exit, so the method returns 4.

The cost is the same as the chapter’s queue search: $O(R\times C)$ time and space, with the distance array in place of visited.