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.

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)

BFS on the grid guarantees the first time you reach the target is the shortest path length.

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

• Invariant: all cells dequeued at distance d have the shortest path length d.
• BFS explores nodes in increasing distance from the sources.
• The first time a node is visited is its shortest distance.
• Therefore the recorded distance/level is optimal.

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.

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.