Lesson 22.3 · Depth-First Search
Working Inward from the Border
When the question is "which cells can reach the edge?", reverse it: start DFS from the edge and mark everything reachable.
10 min
Think of it like this
Instead of asking every house whether rainwater from it can reach the sea, start at the sea and walk uphill: every house you can reach that way drains to the sea.
1.Reverse the direction
Checking each cell separately repeats work. Start from all border cells at once, DFS inward with the rule reversed (for water flow, move to neighbours of equal or greater height), and mark what you reach.
Surrounded Regions: 'O' regions touching the border survive; mark them from the border, then flip every unmarked 'O' to 'X'. Pacific Atlantic: run the reverse DFS once from each ocean's border and intersect the two marked sets.
Quick check
Why is reversing better than DFS from every cell?
Remember
- Start from the targets, not the sources.
- Reverse the movement rule.
- Intersect marks for "reaches both".
Common mistakes
- Forgetting to reverse the comparison (≥ instead of ≤).