628. Open the Lock (BFS + Queue)

A lock has four wheels, each showing a digit 0-9 that wraps around; it starts at '0000'. Each move turns one wheel by one. Given a list of deadend states the lock must never show and a target state, return the minimum number of moves to reach the target, or -1 if impossible. The input is JSON {deadends, target}.

Input: JSON {deadends, target}.

Output: Integer — the minimum moves, or -1.

Examples

Input: {"deadends":["0201","0101","0102","1212","2002"],"target":"0202"}
Output: 6
Explanation: A shortest safe path takes 6 moves.

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

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

Constraints

• 0<=deadends<=500

Asked by