Why it works
- Every step costs the same, so cells leave the queue in order of path length: the first time the last cell comes out, its length is the shortest.
- A cell gets its dist when it is first queued and is never queued again, so nothing is counted twice.
- A diagonal counts as one step, so a gap between two walls that touch at a corner is a way through.
Complexity
Time O(n²): each of the n² cells is queued at most once and looks at 8 neighbours. Memory O(n²) for dist and the queue.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗