Find the minimum number of wheel turns needed to open a 4-wheel lock while avoiding dead-end combinations.
You are given a lock with 4 wheels. Each wheel shows one digit from 0 to 9, and the lock starts at 0000.
In one move, you may rotate any single wheel one step forward or backward:
9wraps to00wraps to9
You are also given a list of dead-end combinations. If the lock ever shows a dead-end combination, it becomes unusable.
Return the minimum number of moves required to reach the target combination from 0000. If it is impossible, return -1.
This is a shortest-path problem on an implicit state graph, where each combination is a node and each valid wheel rotation is an edge.
Input Format
Input
- A list of dead-end combinations, each a 4-character string of digits.
- A target combination, a 4-character string of digits.
Interpretation
- Start state is always
0000. - A move changes exactly one wheel by
+1or-1with wraparound. - Any state in the dead-end list cannot be entered.
Output Format
Output
- Return the minimum number of moves to reach the target from
0000. - Return
-1if the target is unreachable.
Constraints
- There are at most 10,000 possible lock states.
- Each state is a 4-digit string from
0000to9999. - Dead-end states and the target are valid 4-digit combinations.
- The answer fits in a 32-bit signed integer.
Example 1
Input
deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output
6
Explanation
One shortest path is 0000 -> 0001 -> 0002 -> 0102 (blocked, so this path is invalid). A valid shortest route found by BFS takes 6 moves, for example via 0000 -> 1000 -> 1100 -> 1200 -> 1201 -> 1202 -> 0202.
Example 2
Input
deadends = ["8888"], target = "0009"
Output
1
Explanation
Rotate the last wheel backward once: 0000 -> 0009.
Show 1 more example
Example 3
Input
deadends = ["0000"], target = "8888"
Output
-1
Explanation
The starting state is blocked, so the lock cannot be opened.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.