Shortest Path in Binary Matrix

Given an n x n binary matrix, return the length of the shortest path from the top-left to the bottom-right cell, moving in 8 directions. You can only move through cells with value 0. If no path exists, return -1. The path length counts the number of cells in the path.

Why this is worth learning

The graph uses eight directions, and the path length counts cells. A clear 1x1 board therefore has length 1. These choices differ deliberately from the island and rotting-orange problems.

Before coding: one-minute experiment

For [[0,1],[1,0]], is there a path? What length would four-direction code incorrectly return?

Function signature

func ShortestPathBinaryMatrix(grid [][]int) int

Inputs / outputs

• grid: square matrix of 0s and 1s.
• Return: length of shortest clear path, or -1.

Example

grid = [[0,1],[1,0]]
Output: 2

Constraints

• 1 <= n <= 100

Core idea (near-solution)

A recursive route search can enumerate many paths through the same cell; the first route found need not be shortest. Since every legal eight-direction move costs one, process cells in distance layers and retain each cell's first discovery. Validate both endpoints before enqueueing the start, including the one-cell case. The distance counts cells, so the initial clear cell contributes 1. A separate visited set or in-place marking can suppress repeated states; the supplied reference uses the grid, so this API permits that mutation.

Invariant: all cells dequeued at distance d have the shortest path length d.

Algorithm (step-by-step)

1. If grid[0][0] == 1 or grid[n-1][n-1] == 1, return -1.
2. BFS from (0,0) with distance 1.
3. For each cell, explore 8 neighbors that are inside bounds and have value 0.
4. Mark neighbors as visited when enqueuing.
5. When reaching (n-1, n-1), return its distance.
6. If BFS finishes without reaching target, return -1.

Correctness sketch

The start is enqueued at distance one only when both endpoints are clear. Every generated move joins adjacent clear cells in one of the eight allowed directions. Marking a cell on enqueue prevents repeated discovery. FIFO ordering means a cell first reached at distance d cannot have an unprocessed shorter path: that path would have arrived from a previously processed layer. Thus the first target state has the minimum cell count. If the queue empties without it, every reachable clear cell has been explored and no legal path exists.

Trace (hand walkthrough)

Example input:
grid = [[0,1],[1,0]]
Output: 2

Walk:
- start (0,0) distance 1
- diagonal to (1,1) is open -> distance 2
- reach target with length 2

Pitfalls to avoid

• Marking visited only on dequeue (can cause duplicates).
• Forgetting diagonal moves (8 directions).
• Returning the number of edges instead of number of cells.

Debugging lens

Check both endpoints before starting. Keep the eight-direction rule and cell-count distance visible in tests. The visited mark changes 0 to 1, so do not expect the board to remain unchanged.

Complexity

• Time: O(n^2).
• Extra space: O(n^2) for visited/queue.

Implementation notes (Go)

• You can mark visited by setting grid[r][c] = 1 when enqueuing.
• Use a small array of 8 direction offsets.

Contract precision

The input is a nonempty square grid. The reference uses it as visited storage and may change reachable 0 cells to 1; callers needing preservation must copy it.

Reconstruction checkpoint

For the 4×4 grid with zeros only on its main diagonal and ones elsewhere, give a shortest route and its reported length. What changes if moves are restricted to four directions?

Return to Graph BFS · Module quiz