Interview Questions/Coding/Rotary Lock Rescue

Rotary Lock Rescue

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Rotary Lock Rescue

A recovery console controls a four-wheel rotary lock that starts at passcode 0000. In one move, exactly one wheel can be rotated up or down by one digit, wrapping between 9 and 0. Some passcodes are blocked and cannot be used. If the console reaches a blocked passcode, the attempt fails. Determine the fewest safe moves needed to reach the target passcode. Input Format: You are given an array blocked and a string target. Output Format: Return the minimum number of moves needed to reach target, or -1 if it cannot be reached.

Examples

Example 1

Input:

blocked = ["0201", "0101", "0102", "1212", "2002"]
target = "0202"

Output:

Explanation: One shortest turn sequence is 0000 -> 9000 -> 9100 -> 9200 -> 9201 -> 9202 -> 0202. It has 6 move(s), so the output is 6.

Approach hint

The state graph has at most 10000 nodes.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp