Solution: Recovering the Path

To recover the path, we record which neighbor each cell was first reached from.

Let’s add a cameFrom 2D array of Position objects to the search and record a link when a neighbor is first reached. Everything else is the same as the queue-based search from the chapter.

public static List<Position> pathToExit(char[][] maze) {
  if (!isOpen(maze, 0, 0)) {
    return new ArrayList<>();  // empty: no route
  }

  int rows = maze.length;
  int cols = maze[0].length;
  Position[][] cameFrom = new Position[rows][cols];
  boolean[][] visited = new boolean[rows][cols];

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

  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 reconstruct(cameFrom, current);
    }

    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) && !visited[nextRow][nextCol]) {
        visited[nextRow][nextCol] = true;
        cameFrom[nextRow][nextCol] = current;  // remember the way back
        toExplore.enqueue(new Position(nextRow, nextCol));
      }
    }
  }

  return new ArrayList<>();  // empty: the exit is unreachable
}

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

The links point backward, from each cell to the one before it, so following them from the exit traces the route in reverse. To return a path that runs start to exit, we push the cells onto a stack and pop them off, which returns them in reverse order:

private static List<Position> reconstruct(Position[][] cameFrom, Position exit) {
  Stack<Position> stack = new ArrayStack<>();
  for (Position at = exit; at != null; at = cameFrom[at.row][at.col]) {
    stack.push(at);
  }

  List<Position> path = new ArrayList<>();
  while (!stack.isEmpty()) {
    path.add(stack.top());
    stack.pop();
  }
  return path;
}

Let’s trace the method on the following maze. The search begins with the start cell marked visited and in the queue. Every cameFrom entry is null:

┌───┬───┬───┐       ┌────────┬────────┬────────┐
│ S │   │   │       │  null  │  null  │  null  │
├───┼───┼───┤       ├────────┼────────┼────────┤
│ █ │ █ │   │       │  null  │  null  │  null  │
├───┼───┼───┤       ├────────┼────────┼────────┤
│   │   │ E │       │  null  │  null  │  null  │
└───┴───┴───┘       └────────┴────────┴────────┘
    maze                      cameFrom

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

Each time a cell is dequeued, every open neighbor not visited yet gets a link back to that cell. After (0, 1) is dequeued, cameFrom[0][1] holds (0, 0) and cameFrom[0][2] holds (0, 1). The cell at the front of the queue is (0, 2):

┌───┬───┬───┐       ┌────────┬────────┬────────┐
│ S │[ ]│   │       │  null  │ (0, 0) │ (0, 1) │
├───┼───┼───┤       ├────────┼────────┼────────┤
│ █ │ █ │   │       │  null  │  null  │  null  │
├───┼───┼───┤       ├────────┼────────┼────────┤
│   │   │ E │       │  null  │  null  │  null  │
└───┴───┴───┘       └────────┴────────┴────────┘
    maze                      cameFrom

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

After (1, 2) is dequeued, cameFrom[2][2] holds (1, 2). The exit (2, 2) is now at the front of the queue:

┌───┬───┬───┐       ┌────────┬────────┬────────┐
│ S │   │   │       │  null  │ (0, 0) │ (0, 1) │
├───┼───┼───┤       ├────────┼────────┼────────┤
│ █ │ █ │[ ]│       │  null  │  null  │ (0, 2) │
├───┼───┼───┤       ├────────┼────────┼────────┤
│   │   │ E │       │  null  │  null  │ (1, 2) │
└───┴───┴───┘       └────────┴────────┴────────┘
    maze                      cameFrom

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

When (2, 2) is dequeued, it is the exit, so the method calls reconstruct. Notice the start keeps its null entry, because no cell comes before it:

┌───┬───┬───┐       ┌────────┬────────┬────────┐
│ S │   │   │       │  null  │ (0, 0) │ (0, 1) │
├───┼───┼───┤       ├────────┼────────┼────────┤
│ █ │ █ │   │       │  null  │  null  │ (0, 2) │
├───┼───┼───┤       ├────────┼────────┼────────┤
│   │   │[E]│       │  null  │  null  │ (1, 2) │
└───┴───┴───┘       └────────┴────────┴────────┘
    maze                      cameFrom

reconstruct starts at the exit (2, 2) and follows the links: (2, 2) came from (1, 2), which came from (0, 2), which came from (0, 1), which came from (0, 0). It pushes each cell as it reaches it. The entry for (0, 0) is null, so the loop stops there. The start is now on top of the stack:

┌────────┐
│ (0, 0) │ ◀── top
├────────┤
│ (0, 1) │
├────────┤
│ (0, 2) │
├────────┤
│ (1, 2) │
├────────┤
│ (2, 2) │
└────────┘

Popping the cells one by one adds them to the path in start-to-exit order:

(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2)

The extra cameFrom grid costs another $O(R\times C)$ of space. Reconstruction follows the links along the path once. So the whole method is still $O(R\times C)$ in time and space.