1055. Open the Lock — Minimum Turns

A lock has 4 wheels, each showing a digit 0-9, starting at "0000". Each move turns one wheel up or down by one (9 wraps to 0 and vice versa). Given a list of deadend states the lock must never show, return the minimum number of moves to reach 'target', or -1 if impossible. The input is JSON {deadends, target}.

Input: JSON {deadends, target}.

Output: Integer — minimum moves, or -1.

Examples

Input: {"deadends":["0201","0101","0102","1212","2002"],"target":"0202"}
Output: 6
Explanation: Shortest safe sequence of turns.

Input: {"deadends":["8888"],"target":"0009"}
Output: 1
Explanation: One turn.

Input: {"deadends":["0000"],"target":"8888"}
Output: -1
Explanation: Start is a deadend.

Constraints

• 0<=deadends<=500
• target is 4 digits

Asked by