Shortest Path in Binary Matrix

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Given an n × n grid of 0s (open) and 1s (blocked), return the number of cells on the shortest path from the top-left cell to the bottom-right cell, moving through open cells only. From a cell you may step to any of its 8 neighbours (including diagonals). If either corner is blocked or no path exists, return −1.

    The classic "shortest path in a grid" question: every move costs the same, so BFS is the whole answer, and the interview is about getting the details right (directions, start cell, visited marking). Original problem: LeetCode 1091.

    Example

    Using two diagonal steps, the path from the top-left to the bottom-right corner visits 5 cells.
    Using two diagonal steps, the path from the top-left to the bottom-right corner visits 5 cells.
    grid = [[0, 0, 0, 1],
            [1, 1, 0, 1],
            [1, 1, 0, 0],
            [1, 1, 1, 0]]
    Output: 5        # (0,0) (0,1) (1,2) (2,3) (3,3)
    grid = [[1, 0],
            [0, 0]]
    Output: -1       # the start cell is blocked

    Constraints (assumed)

    • 1 ≤ n ≤ 100; each cell is 0 or 1.

    What this question tests

    • Seeing the grid as a graph with unit-cost edges, so BFS gives shortest paths.
    • Exact details: 8 directions, bounds checks, visited when enqueued, blocked corners.
    • Knowing what changes for weighted cells (Dijkstra) or guided search (A*).

    Questions to ask first

    1. Which moves are allowed? (Here: 8 directions. Many grid problems use 4.)
    2. Do we count cells or steps? (Here: cells, so a 1 × 1 open grid returns 1.)
    3. Can I modify the grid to mark visited cells? If not, use a separate set.
    4. Is the grid always square? (Here: yes; the code works for rectangles with small changes.)