The problem
In an n×n grid of 0s (open) and 1s (blocked), find the length of the shortest clear path from the top-left to the bottom-right, moving in all 8 directions. Return −1 if none exists.
Stuck? Reveal hints one at a time
How to approach it
- 1If the start or end cell is blocked, return −1 immediately.
- 2BFS from (0,0) with distance 1; mark cells visited as you enqueue (not as you dequeue).
- 3Explore all 8 neighbors; first time (n−1, n−1) is reached, its distance is the answer.
- 4Queue exhausted without reaching the end → −1.
Key insight
Mark-on-enqueue prevents the same cell entering the queue multiple times — the classic grid-BFS performance bug is marking on dequeue.
The solution
Watch out for
- Eight directions, not four — diagonal moves are allowed here.
- The 1×1 grid with a clear cell answers 1 (the start IS the end).