Problem context and objectives
Mission briefing
Expedition navigator · Safe camps and hazards form a connected world map
Find a valid route while marking every place already explored: Signal Reach.
Without visited state, the party loops forever or revisits expensive terrain.
How you win
- 1Recognize when Reachability by depth-first search matches the clues
- 2Keep this true after every move: every node in seen is reachable from the start and no node is expanded twice
- 3Reach the result within O(V + E) time and O(V) space
Rules and pressure
- Target cost: O(V + E) time and O(V) space
- State rule: every node in seen is reachable from the start and no node is expanded twice
Lesson 1 of 3
Choose the unseen frontier across every new edge.
Your call · Nodes 1 and 2 are unseen neighbors of node 0. When should they be marked seen?