Solution: Counting Cells with a Stack

You can implement this by modifying any of the maze search algorithms we have seen. The order in which we count the reachable cells does not matter. The method only needs to count each reachable open cell once. I use the stack-based search here.

Let’s count a cell when we pop it. We will mark it visited when we push it, so the same cell cannot be pushed twice.

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

  int rows = maze.length;
  int cols = maze[0].length;
  boolean[][] visited = new boolean[rows][cols];
  Stack<Position> toExplore = new ArrayStack<>();

  toExplore.push(new Position(0, 0));
  visited[0][0] = true;

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

  while (!toExplore.isEmpty()) {
    Position current = toExplore.top();
    toExplore.pop();
    count++;

    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]) {
        toExplore.push(new Position(nextRow, nextCol));
        visited[nextRow][nextCol] = true;
      }
    }
  }

  return count;
}

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

The method returns 0 immediately if the start cell (0, 0) is a wall.

Let’s trace the method on the following maze. The start cell is pushed and marked visited, and the stack holds just that one cell:

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

┌────────┐
│ (0, 0) │ ◀── top
└────────┘

Partway through the search, (1, 1) is the cell we just popped, shown in brackets. The method has counted three cells so far: (0, 0), (1, 0), and (1, 1). It pushed the open neighbor (2, 1) onto the stack and marked it visited, and (0, 1) is still below it. Both cells on the stack are marked visited, but neither one has been counted yet:

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

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

The search ends when the stack is empty. Every open cell reachable from the start has been popped and counted, so count is 6:

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

(empty stack)

The cost is the same as the chapter’s stack search: $O(R\times C)$ time and space for a maze with $R$ rows and $C$ columns.