Queue Search and Cost

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. A move cannot go off the maze or 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 queue is the Queue ADT, with this interface. LinkedQueue implements it.

public interface Queue<T> {
  void enqueue(T item);  // adds item to the back
  void dequeue();        // removes the front item
  T front();             // returns the front item
  boolean isEmpty();     // true if the queue has no items
}

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

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

  boolean[][] visited = new boolean[maze.length][maze[0].length];
  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 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.enqueue(new Position(nextRow, nextCol));
        visited[nextRow][nextCol] = true;
      }
    }
  }

  return false;
}
Solution

The dequeues, in order, are (0,0), (0,1), (1,0), (0,2), (2,0), (0,3), (1,2), (2,1), (2,2), (2,3). When (2,3) is dequeued, isExit is true and the method returns true with the queue empty.

Step by step, with the queue written front to back:

Dequeue Enqueues Queue after
(0,0) (0,1), (1,0) (0,1), (1,0)
(0,1) (0,2) (1,0), (0,2)
(1,0) (2,0) (0,2), (2,0)
(0,2) (0,3), (1,2) (2,0), (0,3), (1,2)
(2,0) (2,1) (0,3), (1,2), (2,1)
(0,3) nothing (1,2), (2,1)
(1,2) (2,2) (2,1), (2,2)
(2,1) nothing (2,2)
(2,2) (2,3) (2,3)
(2,3) exit, return true empty
Solution
  • Distance 0: (0,0)
  • Distance 1: (0,1), (1,0)
  • Distance 2: (0,2), (2,0)
  • Distance 3: (0,3), (1,2), (2,1)
  • Distance 4: (2,2)
  • Distance 5: (2,3)

Every cell at one distance is dequeued before any cell at the next distance. The queue removes cells in the order they were added, and a cell at distance is only enqueued when a cell at distance is dequeued, so it goes behind every closer cell already in the queue.

Solution

All three run in time: each cell is marked visited at most once, so each cell is processed at most once, and processing a cell checks at most four neighbors.

All three use space: the visited array has entries, the call stack holds at most frames, and the explicit stack or the queue holds at most cells at once.