← DSA Atlas
Dedicated problem page · #1091

Shortest Path in Binary Matrix

MediumGraph DFS and BFSShortest path in an unweighted gridBFS with 8-directional moves
Solve on LeetCode ↗
1091
MediumGraph DFS and BFSBFS with 8-directional movesShortest path in an unweighted grid

Shortest Path in Binary Matrix

Given an n x n binary matrix, a clear path runs from the top-left cell (0,0) to the bottom-right cell (n-1,n-1) through cells valued 0, moving in any of the 8 directions between adjacent (including diagonal) cells. Return the length of the shortest clear path measured in number of visited cells, or -1 if none exists.

Open official problem prompt ↗
In plain English

Compute the minimum number of cells on a clear top-left-to-bottom-right path where movement includes diagonals, or report that none exists.

Picture it like this

A king on a chessboard walks from one corner to the opposite corner across open squares, taking one step per move in any of eight directions. You want the fewest squares the king must touch.

Example
Input
grid = [[0,0,0],[1,1,0],[1,1,0]]
Output
4
Why
The path (0,0) -> (0,1) -> (1,2) -> (2,2) visits 4 cells and is the shortest clear route to the corner.
Constraints
n == grid.length == grid[i].length1 <= n <= 100grid[i][j] is 0 or 1
Pattern lesson

See the pattern, then code

Shortest path in an unweighted grid
Recognition clue

Shortest path length between two cells in an unweighted grid, with all moves costing one step — the textbook signal for BFS. The only nuance is 8 neighbors instead of 4.

↗
Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Because every step (orthogonal or diagonal) costs one, BFS from the start expands cells in increasing distance, so the corner is first reached along a shortest route. Mark cells visited by overwriting them so the queue never revisits a cell.

New words, made simpleKnow these before the algorithm
Clear cell
A cell valued 0 that a path may pass through.
8-directional move
A step to any of the up-to-8 adjacent cells, diagonals included.
Path length
The count of cells visited, including both endpoints.
Visited marking
Overwriting a cell to 1 once enqueued so it is not processed twice.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
DFS exploration

Does not naturally produce the minimum and risks exploring exponentially many routes.

Recursively explore paths tracking the shortest completion.

Time Exponential without careful pruningSpace O(n^2)
Best choiceBFS from the start

Uniform step cost makes the first arrival at the corner optimal; each cell visited once.

Layered expansion over 8 neighbors, marking cells visited on enqueue.

Time O(n^2)Space O(n^2)
The rule we keep true

Invariant

When a cell is dequeued, its stored dist equals the minimum number of cells on a clear path from the start to that cell.

Why this is correct

Reasoning

All moves cost exactly one, so BFS discovers cells in non-decreasing distance. Marking a cell visited the moment it enters the queue guarantees each cell is expanded once and along a shortest route, so the corner's first dequeue yields the minimum path length; an empty queue means the corner is unreachable.

The algorithm in three movesSay these aloud before coding
1Return -1 if the start or the end cell is blocked (value 1)

queue: (0,0,1)

2Seed the queue with (0,0,1) — distance counts cells including the start

layer 2: (0,1,2)

3Pop a cell; if it is the bottom-right corner return its distance

layer 3: (1,2,3) via diagonal

4Push every in-bounds, value-0 neighbor among the 8 directions, marking it 1 as visited

reach (2,2,4) -> return 4

5Return -1 if the queue drains without reaching the corner

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
S0
01
02
13
14
05
16
17
E8
1 · Readgrid[0][0], grid[n-1][n-1]
2 · AskEndpoints open?
3 · Update stateboth are 0
4 · ResultProceed with BFS.
Key takeaway

3x3 grid: BFS reaches the bottom-right corner in 4 cells using one diagonal step.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-5Endpoint guard

    If either corner is blocked no clear path can start or finish, so return -1 immediately.

  2. 2
    Lines 6-10Direction list and seeding

    All 8 offsets enable diagonal moves; distance starts at 1 because the path length counts the start cell, and grid[0][0] is marked visited.

  3. 3
    Lines 15-20Neighbor expansion

    Each in-bounds open neighbor is marked visited and enqueued at dist+1, guaranteeing single processing and correct layering.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • 1x1 grid with value 0 -> path length 1
  • Start or end cell is 1 -> return -1
  • Fully blocked interior with no route -> return -1
  • Grid where the straight diagonal is entirely open -> length n
!

Common beginner mistakes

  • Using 4 directions instead of 8 and overcounting the path length
  • Starting the distance at 0 instead of 1 (the problem counts cells, not edges)
  • Marking a cell visited at dequeue time, which lets duplicates pile up in the queue
  • Skipping the endpoint blocked-check and doing needless BFS
Check your understanding

Why does BFS, rather than Dijkstra, suffice here even though diagonal moves are allowed?

More in Graph DFS and BFS

#200Number of IslandsGrid flood fill#133Clone GraphGraph traversal with clone map#994Rotting OrangesMulti-source BFS (level-by-level)#127Word LadderShortest transformation via BFS#130Surrounded RegionsBorder-guarded flood fill#286Walls and GatesMulti-source BFS distance fill