Searching with a Stack

The maze is a char[][] where '#' is a wall and any other character is an open cell. The start is (0, 0) and the exit is the bottom-right cell. One move goes up, right, down, or left by one step, never off the maze and never into a wall.

Two helpers are already written. isOpen(maze, row, col) returns true when (row, col) is inside the maze and not a wall. isExit(maze, row, col) returns true when (row, col) is the exit.

A cell is held as a Position:

private static class Position {
  int row;
  int col;

  Position(int row, int col) {
    this.row = row;
    this.col = col;
  }
}

The stack is the Stack ADT, with this interface. ArrayStack implements it.

public interface Stack<T> {
  void push(T item);  // adds item to the top
  void pop();         // removes the top item
  T top();            // returns the top item
  boolean isEmpty();  // true if the stack has no items
}

The search considers the four directions in the order right, down, left, up.

Solution
public static boolean hasPathWithStack(char[][] maze) {
  if (!isOpen(maze, 0, 0)) {
    return false;
  }

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

  toExplore.push(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.top();
    toExplore.pop();

    if (isExit(maze, current.row, current.col)) {
      return true;
    }

    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 false;
}
Solution

Two cells can share an unvisited neighbor. If the search waits until the pop to mark a cell, the first cell pushes the neighbor, and the second cell still sees it unmarked and pushes it again. The same cell then sits on the stack twice and is explored twice.

Solution

The call stack. The call on top holds the cell being processed. Making a recursive call on a neighbor is the push. A call returning is the pop, and control goes back to the call directly beneath it.

Solution

A paused recursive call remembers where it is in its || expression, so it knows which direction to try next. A cell on the stack is only a pair of coordinates. It does not record which neighbors have been tried, so all of them are pushed when the cell is processed.

Solution

The pops, in order, are (0,0), (1,0), (2,0), (2,1), (2,2), (1,2), (0,2), (0,3), (2,3). When (2,3) is popped, isExit is true and the method returns true with (0,1) still on the stack.

Step by step, with the stack written bottom to top:

Pop Pushes Stack after
(0,0) (0,1), (1,0) (0,1), (1,0)
(1,0) (2,0) (0,1), (2,0)
(2,0) (2,1) (0,1), (2,1)
(2,1) (2,2) (0,1), (2,2)
(2,2) (2,3), (1,2) (0,1), (2,3), (1,2)
(1,2) (0,2) (0,1), (2,3), (0,2)
(0,2) (0,3) (0,1), (2,3), (0,3)
(0,3) nothing (0,1), (2,3)
(2,3) exit, return true (0,1)
Solution

No. The stack search pushes the neighbors in the order right, down, left, up, so it pops them in the order up, left, down, right. On the maze above, the recursive search moves from the start to (0,1) first, while the stack search pops (1,0) first. The stack search also marks a cell visited when it pushes it, so a cell can be marked long before the search pops it, and the search does not push it again when the cell later shows up as the neighbor of another cell. Both find a path when one exists, but they can reach the exit by different routes.