Shortest Path in Binary Matrix

Problem

Robot navigation systems must plan obstacle-free routes through grid-based maps. Given a binary grid where 0 is passable and 1 is blocked, find the minimum number of cells the robot must traverse to travel from top-left to bottom-right with 8-directional movement. The cell count includes start and end; return -1 if no path exists.

[[0,1],   → -1 (no clear path)
 [1,0]]
 
[[0,0,0], → 4
 [1,1,0],
 [1,1,0]]
 
[[0,0],   → 2
 [0,0]]

Solution

Approach: grid BFS with 8-directional moves, carrying the path length in the queue.

Every move costs one step regardless of direction, so the grid is an unweighted graph and BFS finds the shortest route. We carry the running path length in each queue tuple - (row, col, path_length) - seeded at (0, 0, 1) because the start cell itself counts toward the length. On each pop we first check whether we are at the destination (rows-1, cols-1); if so we return path_length immediately, since BFS dequeues cells in nondecreasing distance order and the first arrival at the target is therefore optimal. Otherwise we expand all 8 neighbors, enqueuing each valid one at path_length + 1.

A neighbor is valid only if it is in bounds, its value is 0 (passable), and it is not already visited. We add it to visited the moment we enqueue it - marking on dequeue would let several neighbors queue the same cell and inflate the queue with duplicates. The bounds check must come before indexing grid[next_row][next_col] so an out-of-range coordinate never raises. On [[0,1],[1,0]] BFS steps diagonally from (0,0) to (1,1) in one move, returning length 2.

Edge cases: a blocked start or end (grid[0][0] == 1 or the corner is 1) returns -1 before the loop runs. A 1x1 clear grid returns 1, since the start is already the destination. If the queue empties without reaching the corner, no clear path exists and we return -1.

Complexity: O(n^2) time and space on an n x n grid - each cell is enqueued at most once and has a constant 8 neighbors to scan.