Move through open cells (0) from top-left to bottom-right, stepping in any of
8 directions (including diagonals). Return the number of cells on the shortest path,
or -1 if there's none.
The BFS idea → BFS explores cells in order of distance from the start, so the
first time it touches the target, that's guaranteed to be the shortest path - no need
to look further. Each cell stores its distance = parent's distance + 1. The numbers you see
are "how many cells to reach me". The gold trail is rebuilt by walking parents back from the goal.
Grid (number = distance from start)
open (0)blocked (1)startfrontiervisitedshortest path
What's happening
Queue (FIFO →)
Counters
Code
Complexity: O(n²) time and space - each cell is visited once, 8 neighbour checks each. ·
Why BFS, not DFS: BFS dequeues cells in non-decreasing distance order, so the goal is
reached by a shortest route first. DFS would find a path, not the shortest.