The problem
A 4-wheel lock starts at "0000". One move turns one wheel ±1 (wrapping 9↔0). Avoid deadend combinations entirely. Return the fewest moves to reach the target, or −1.
Stuck? Reveal hints one at a time
How to approach it
- 1Put deadends in a set; if it contains "0000" (or the start is the target trivially), handle immediately.
- 2BFS from "0000", generating 8 neighbors per state (4 wheels × 2 directions).
- 3Skip deadends and visited states; mark visited on enqueue.
- 4Return the depth when the target appears; −1 if BFS exhausts.
Key insight
Recognizing the implicit graph is the entire problem — once "combination = node, turn = edge" clicks, this is textbook BFS with a blocklist.
The solution
Watch out for
- "0000" in deadends must return −1 before any search.
- Bidirectional BFS cuts the frontier dramatically — the go-to answer for the follow-up.