Shortest Path in a Binary Matrix | Leetcode 1091 | Dijkstra’s Algorithm with Normal Queue (BFS)

Find the shortest clear path from the top-left to bottom-right of a 0-1 grid. We explain the intuition, walk through an 8-direction BFS, add comments to every line of code, show a dry run, and give the exact time and space costs.

Here’s the [Problem Link] to begin with.

1. What does the problem ask?

Given an n × n binary matrix grid:

• 0 means an open cell you can walk on.
• 1 means a blocked cell you cannot step on.

You start at cell (0,0) and want to reach cell (n-1,n-1).
You may move to any of the 8 neighbouring cells (up, down, left, right, and the four diagonals) as long as the destination cell contains 0.

Return the length of the shortest such path (counting both start and end cells).
If no path exists, return -1.

2. Example

grid = [
  [0,1,0],
  [1,0,1],
  [1,0,0]
]

The shortest clear path is:

(0,0) → (1,1) → (2,2)

Path length = 3.
shortestPathBinaryMatrix(grid) returns 3.

3. Intuition & approach

3.1 Why Breadth-First Search (BFS)?

• All moves have the same cost (1 step).
• BFS explores level by level:
  • Level 1: start cell.
  • Level 2: all cells one step away.
  • Level 3: two steps away, and so on.
• The first time BFS reaches the bottom-right cell, that distance is already the shortest possible.

3.2 Eight directions

At each cell we can move to any of these offsets:

(-1, 0)  (-1,-1)  (-1, 1)
( 0,-1)   ...     ( 0, 1)
( 1, 0)  ( 1,-1)  ( 1, 1)

Checking bounds and blocked cells avoids invalid steps.

3.3 Distance grid

We keep a 2-D array distance:

• distance[i][j] = shortest path length found so far to reach (i,j).
• Initialize all to ∞ except distance[0][0] = 1.
• Update a neighbour only if the new length is smaller than its stored value.

We can also early-return when the end cell is popped or updated, saving work.

4. Code

import sys
from collections import deque


class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        # Blocked start means no path
        if grid[0][0] == 1:
            return -1

        rows = len(grid)
        cols = len(grid[0])

        # distance matrix – start cell has distance 1
        distance = [[sys.maxsize for _ in range(cols)] for _ in range(rows)]
        distance[0][0] = 1

        queue = deque()
        queue.append([1, 0, 0])        # [current_dist, row, col]

        while queue:
            dist, i, j = queue.popleft()

            # 8 possible moves
            for x, y in [
                [1, 0],   [0, -1],  [-1, 0],  [0, 1],
                [-1, -1], [-1, 1],  [1, 1],   [1, -1],
            ]:
                new_i, new_j = i + x, j + y

                # skip if out of bounds
                if new_i < 0 or new_i >= rows or new_j < 0 or new_j >= cols:
                    continue
                # skip if blocked
                if grid[new_i][new_j] == 1:
                    continue

                new_dist = dist + 1
                # relax distance
                if new_dist < distance[new_i][new_j]:
                    # if we reached the goal, return immediately
                    if new_i == rows - 1 and new_j == cols - 1:
                        return new_dist
                    distance[new_i][new_j] = new_dist
                    queue.append([new_dist, new_i, new_j])

        # If end cell still at ∞, no path exists
        return -1 if distance[rows - 1][cols - 1] == sys.maxsize else distance[rows - 1][cols - 1]

5. Line-by-line explanation

1. Start check – if (0,0) is blocked, we cannot even step on the grid.
2. distance matrix – carries best path lengths; sentinel sys.maxsize means “unreached”.
3. Queue – each entry holds current known path length plus coordinates.
4. BFS loop – pops the next cell in FIFO order (shortest distance first).
5. For each neighbour:
   • Bounds and block checks.
   • Compute new_dist = dist + 1.
   • If this is better, store it and push the neighbour.
   • Early exit when we first reach (rows-1, cols-1).
6. After BFS, if the bottom-right distance is still ∞, return -1; otherwise return that distance.

6. Dry run on the example grid

Path length returned = 3.

7. Complexity

n is the grid size (rows = cols).

8. Conclusion

• BFS is ideal when every move costs the same.
• Track a distance grid and relax only when you truly shorten a path.
• Because movement is allowed in eight directions, simple Manhattan BFS won’t work—you must include diagonals.
• Early-return as soon as you touch the goal cell to avoid needless work.

With this pattern you can quickly adapt to maze-like problems that ask for the length of the shortest clear path in a binary matrix.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.