☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Shortest Distance in a Binary Maze

Hard TUF ID 527 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an n × m grid of 0s and 1s, a source cell and a destination cell. A cell with value 1 can be walked on and a cell with value 0 is a wall. From any cell you may move one step up, down, left or right (no diagonals) onto another walkable cell inside the grid. Return the minimum number of steps from the source to the destination, or -1 if the destination cannot be reached. If the source and destination are the same walkable cell, the answer is 0; if either one is a wall, the answer is -1.

Constraints: 1 ≤ n, m ≤ 500.

Example 1

grid = 1 1 1 1          source = (0, 1)
       1 1 0 1          destination = (2, 2)
       1 1 1 1
       1 1 0 0
       1 0 0 1
answer = 3               // (0,1) → (1,1) → (2,1) → (2,2)

Example 2

grid = 1 1 1 1 1        source = (0, 0)
       1 1 1 1 1        destination = (3, 4)
       1 1 1 1 0
       1 0 1 0 1
answer = -1              // (3,4) is boxed in by the walls at (2,4) and (3,3)

Modelling. Each walkable cell is a node, and two walkable cells that share a side are joined by an edge of length 1. The question is a single-source shortest path in an unweighted graph. The grid is the graph; we never build an adjacency list, we just try the four directions stored in DR and DC.

static final int[] DR = {-1, 0, 1, 0}, DC = {0, 1, 0, -1};

Approach 1: Brute force, try every path

Intuition. Walk from the source in every possible way that never revisits a cell on the current path, and remember the shortest walk that reaches the destination. This is backtracking: mark a cell as “on the path” when you step onto it and clear the mark when you step back, so other paths may use it. One cheap pruning helps a lot: once a partial path is already as long as the best complete one, it cannot improve the answer.

Algorithm.

  1. If the source or destination is a wall, return -1.
  2. explore(r, c, steps): stop if steps ≥ best. If (r, c) is the destination, record steps.
  3. Otherwise mark (r, c), recurse into each open, unmarked neighbour with steps + 1, then unmark.
  4. Return best, or -1 if it was never set.
static int bruteForce(int[][] grid, int[] src, int[] dst) {
    if (grid[src[0]][src[1]] == 0 || grid[dst[0]][dst[1]] == 0) return -1;
    int[] best = {Integer.MAX_VALUE};
    explore(grid, src[0], src[1], dst, 0, new boolean[grid.length][grid[0].length], best);
    return best[0] == Integer.MAX_VALUE ? -1 : best[0];
}

static void explore(int[][] grid, int r, int c, int[] dst, int steps, boolean[][] onPath, int[] best) {
    if (steps >= best[0]) return;                         // cannot beat the best path found so far
    if (r == dst[0] && c == dst[1]) {
        best[0] = steps;
        return;
    }
    onPath[r][c] = true;
    for (int k = 0; k < 4; k++) {
        int nr = r + DR[k], nc = c + DC[k];
        if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length
                && grid[nr][nc] == 1 && !onPath[nr][nc]) {
            explore(grid, nr, nc, dst, steps + 1, onPath, best);
        }
    }
    onPath[r][c] = false;                                 // free the cell for other paths
}

Complexity. Time is exponential in the number of cells: an open n × m grid has an astronomical number of self-avoiding paths, and the pruning only trims them. Space O(n × m) for the marks and the recursion. Fine for a 5 × 5 test grid, hopeless for 500 × 500.

Approach 2: Better, Dijkstra on the grid

Intuition. Shortest path from one source is Dijkstra’s job. Keep the best known distance of every cell, a min-heap of {dist, row, col}, and always expand the closest cell first. The first time the destination is popped, its distance is final, so we can return right away. This is how the problem is often presented in the Dijkstra section, and the code transfers unchanged to grids where moves cost different amounts.

Algorithm.

  1. Handle walls at the endpoints. Set dist[src] = 0 and push {0, src}.
  2. Pop the smallest entry. Skip it if stale; return its distance if it is the destination.
  3. For each open neighbour, if d + 1 beats its distance, update it and push.
  4. Return -1 if the heap runs dry.
static int dijkstra(int[][] grid, int[] src, int[] dst) {
    int n = grid.length, m = grid[0].length;
    if (grid[src[0]][src[1]] == 0 || grid[dst[0]][dst[1]] == 0) return -1;
    int[][] dist = new int[n][m];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    dist[src[0]][src[1]] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.add(new int[]{0, src[0], src[1]});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int d = top[0], r = top[1], c = top[2];
        if (d > dist[r][c]) continue;                     // stale heap entry
        if (r == dst[0] && c == dst[1]) return d;
        for (int k = 0; k < 4; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 1 && d + 1 < dist[nr][nc]) {
                dist[nr][nc] = d + 1;
                pq.add(new int[]{d + 1, nr, nc});
            }
        }
    }
    return -1;
}

Complexity. Time O(n × m × log(n × m)): each cell is pushed a bounded number of times (once per improving neighbour) and every heap operation costs a logarithm. Space O(n × m) for distances and the heap.

Intuition. Look at the distances the heap in Approach 2 holds. Every move costs exactly 1, so when a cell at distance d is expanded it pushes neighbours at distance d + 1. The heap therefore never contains anything except values d and d + 1, and taking them in arrival order already takes them in distance order. A plain FIFO queue gives the same order for free. That is BFS, and the log factor disappears.

It also simplifies the bookkeeping. In BFS the first time a cell is discovered it gets its final distance, because everything closer has already been dequeued. So each cell is enqueued exactly once and the distance array doubles as the visited array (-1 means “not reached”).

Algorithm.

  1. Handle walls at the endpoints. Fill dist with -1, set dist[src] = 0 and enqueue the source.
  2. Pop a cell. If it is the destination, return its distance.
  3. For each in-bounds, open neighbour with dist == -1, set dist = current + 1 and enqueue it.
  4. Return -1 when the queue is empty.
static int optimal(int[][] grid, int[] src, int[] dst) {
    int n = grid.length, m = grid[0].length;
    if (grid[src[0]][src[1]] == 0 || grid[dst[0]][dst[1]] == 0) return -1;
    int[][] dist = new int[n][m];
    for (int[] row : dist) Arrays.fill(row, -1);          // -1 = not reached yet
    dist[src[0]][src[1]] = 0;
    Deque<int[]> queue = new ArrayDeque<>();
    queue.add(new int[]{src[0], src[1]});
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        int r = cell[0], c = cell[1];
        if (r == dst[0] && c == dst[1]) return dist[r][c];
        for (int k = 0; k < 4; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 1 && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                queue.add(new int[]{nr, nc});
            }
        }
    }
    return -1;
}

Dry run on Example 1, by BFS layer (cells are (row, col)):

distance cells reached at this distance
0 (0,1)
1 (0,0), (0,2), (1,1)
2 (0,3), (1,0), (2,1)
3 (1,3), (2,0), (2,2), (3,1)

The wall at (1,2) blocks the direct route down from (0,2), so (2,2) is first reached from (2,1) at distance 3. As soon as (2,2) is popped, the method returns 3.

Complexity. Time O(n × m): each cell is enqueued at most once and checks four neighbours. Space O(n × m) for the distance grid and the queue.

Edge cases and pitfalls