In an n × n grid of 0s (open) and 1s (blocked), return the number of cells on the shortest path from the top-left to the bottom-right cell, moving to any of the 8 neighbors, or -1 if there is none.
Before you code
All moves cost the same, so BFS gives shortest paths. Check the start and end cells first: either being blocked means -1.
Hints
- Start from (0, 0) with path length 1.
- Generate the 8 neighbors with a list of direction pairs, skipping out-of-range and blocked cells.
- Mark cells visited when you enqueue them (or set them to 1 in the grid).
Production & complexity notes
When solving Shortest path in binary matrix on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Breadth-first search to reinforce the underlying pattern.
What it practices
BFS on a grid, from Breadth-first search.