Shortest Path in Binary Matrix

Problem

You are given an n x n grid of 0s and 1s. A clear path starts at the top-left cell (0, 0), ends at the bottom-right cell (n-1, n-1), passes only through cells containing 0, and moves between cells that share an edge or a corner (eight directions). The length of a path is the number of cells it visits. Return the length of the shortest clear path, or -1 if there is none.

• The grid is square with at most 150 rows and 150 columns.
• Each cell is 0 or 1.
• If the start or the end cell is 1, no path exists.

Examples

• grid = [[0,0],[1,0]] → 2. One diagonal step from (0,0) to (1,1).
• grid = [[0,0,1],[1,0,1],[1,0,0]] → 3. The only open cells form a single column down the middle plus the two ends: (0,0) -> (0,1) -> (1,1) -> (2,2).
• grid = [[0,1,1],[1,1,0],[1,1,0]] → -1. The open cells at (0,0) and the bottom-right corridor are cut off from each other by a wall of 1s.

Hints

1. All moves cost the same. Which algorithm finds shortest paths when every edge has equal weight?
2. Eight neighbors instead of four changes only one thing in the code. What is it?
3. BFS from (0,0) with a visited grid; the level at which (n-1,n-1) is dequeued (plus one for the start cell) is the answer.