Shortest Path in Binary Maze

Problem Link

Problem Statement

You are given an n × m grid where each cell contains either:

1 → open cell (can traverse)
0 → blocked cell (cannot traverse)

You must find the shortest path length (minimum number of steps) from a given source cell to a destination cell. Moves are allowed in four directions: up, down, left, right. Return -1 if the destination is not reachable.

Algorithmic Intuition: Lee Algorithm (Breadth‑First Search)

This problem is best solved using multi-source BFS on the grid:

Treat each cell as a node in a graph.
An edge exists between adjacent open cells.
BFS guarantees exploring in layers of increasing distance.
As soon as the destination is dequeued from the BFS queue, the current distance is the shortest path.

This method is also known as the Lee algorithm in grid/maze pathfinding.

Algorithm Steps

Check inputs:
- If grid[src.x][src.y] == 0 or grid[dest.x][dest.y] == 0, return -1 immediately.
Initialize:
- A 2D boolean visited array, same size as the grid, all initially false.
- A BFS queue storing QueueNode { x, y, dist }.
Enqueue Source:
- Mark source visited, push (src.x, src.y, 0) into queue.
BFS Loop:
- While the queue is not empty:
  - Pop front node (x, y, dist).
  - If this equals destination, return dist.
  - Otherwise, for each of four neighbor positions (nx, ny):
    - If in grid bounds, cell value is 1, and not visited:
      - Mark visited and enqueue (nx, ny, dist + 1).
If BFS completes without hitting destination, return -1.

Java Code (Grid BFS / Lee Algorithm)

class Solution {
    static class Node {
        int x, y, dist;
        Node(int x, int y, int dist) {
            this.x = x; this.y = y; this.dist = dist;
        }
    }

    public int shortestPath(int[][] grid, int sx, int sy, int dx, int dy) {
        int n = grid.length, m = grid[0].length;
        if (grid[sx][sy] == 0 || grid[dx][dy] == 0) return -1;

        boolean[][] visited = new boolean[n][m];
        Queue<Node> q = new LinkedList<>();
        int[] dx4 = {-1, 0, 0, 1};
        int[] dy4 = {0, -1, 1, 0};

        visited[sx][sy] = true;
        q.add(new Node(sx, sy, 0));

        while (!q.isEmpty()) {
            Node curr = q.poll();
            int x = curr.x, y = curr.y, dist = curr.dist;
            if (x == dx && y == dy) return dist;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx4[i], ny = y + dy4[i];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m
                        && grid[nx][ny] == 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.add(new Node(nx, ny, dist + 1));
                }
            }
        }
        return -1;
    }
}

Dry Run Example

Grid:

1 0 1 1 1
1 1 0 1 1
0 1 1 1 0

Source (0,0), Destination (2,2):

Enqueue (0,0,0)
Pop → enqueue (1,0,1), (0,1) blocked
Next pop (1,0,1) → enqueue (1,1,2)
Pop (1,1,2) → enqueue (2,1,3) and (1,2) blocked
Pop (2,1,3) → enqueue (2,2,4) which matches destination → return 4.

Time and Space Complexity

Metric	Complexity
Time	O(n × m)
Space	O(n × m) for visited and queue

Each cell is visited at most once.
Enqueuing and dequeuing operations happen once per reachable cell.

Why BFS Works—Key Points

BFS explores all nodes at distance d before any at distance d + 1.
When destination is dequeued, it has the minimum number of steps from source.
No weight complications—each step counts as distance increment of one.

Comparison with Other Approaches

DFS/Backtracking: Can explore all paths but does not guarantee shortest path. Potentially exponential time and space.
Dijkstra’s Algorithm: Works for weighted graphs with non-negative weights, but here each movement costs uniformly 1, so BFS is more efficient and simpler.
A*: Could be used for heuristics, but unnecessary for uniform movement cost grids.

When to Use This Template

Binary or unweighted grid/maze with obstacle cells (0/1).
You need shortest number of steps between two grid coordinates.
Movements restricted to orthogonal neighbors.