597. Shortest Path in Binary Matrix
You are given an n x n grid of 0s and 1s. A cell containing 0 is open; a cell containing 1 is blocked.
A clear path starts at the top-left cell (0, 0), ends at the bottom-right cell (n - 1, n - 1), and only ever stands on open cells. From any cell you may step to any of its 8 neighbors — up, down, left, right, or any diagonal — as long as that neighbor is open.
The length of a path is the number of cells it visits, counting both endpoints (so standing still on a 1×1 grid is a path of length 1).
Return the length of the shortest clear path, or -1 if the corners are blocked or no path connects them.
Example 1:
Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Explanation: The left and middle of the lower rows are walls. One shortest route is (0,0) → (0,1) → (1,2) → (2,2), using a diagonal step to cut the corner — 4 cells in total.
Example 2:
Input: grid = [[0,1],[1,0]]
Output: 2
Explanation: Both straight moves out of (0,0) are blocked, but the diagonal neighbor (1,1) is open: two cells, done.
Constraints:
- n == grid.length == grid[i].length
- 1 ≤ n ≤ 100
- grid[i][j] is 0 or 1
Hints:
Think of every open cell as a node and every pair of touching open cells — including diagonal touches — as an edge. All edges cost the same, so "shortest path" means "fewest cells". Which classic traversal finds fewest-edge paths in an unweighted graph?
Run BFS from (0, 0), after first checking that both corners are open. Record each cell's distance when you first reach it and enqueue it; the first time (n-1, n-1) comes off the queue, its distance is the answer. Mark cells visited when you enqueue them, not when you dequeue — otherwise the queue fills with duplicates.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Expected output: 4