Why the flood guarantees the shortest path:

• Every “Spread” fills one ring — all cells exactly d steps from the start.
• Cells at distance d are completely filled before any cell at distance d+1 even gets wet.
• So the first moment water touches the Goal, it arrived via the shortest possible route.
• Greedy/DFS can find a path but may walk past shortcuts and get trapped. The flood misses nothing.

Complexity: O(V + E) — every cell visited once, every passage checked once.