题目描述

你面前有一个带有 $4$ 个拨轮的密码锁，每个拨轮可以在 $0-9$ 之间旋转。每次旋转时，你可以将某个拨轮的数字增加 $1$ 或减少 $1$（$0$ 变成 $9$，$9$ 变成 $0$）。

初始状态是 $0000$，你需要通过最少的旋转次数到达目标状态 $target$。

不过，锁中有一些“死亡数字”（deadends），如果锁的某个状态出现在 $deadends$ 列表中，则该状态不可用，无法旋转到达。

求解 从 $0000$ 变为 $target$ 的最少旋转次数，如果无法解锁，则返回 -1。

输入格式

• 第一行：一个整数 $n$，表示死亡数字的个数。
• 接下来 $n$ 行：每行一个长度为 $4$ 的字符串，表示一个死亡数字。
• 最后一行：一个长度为 $4$ 的字符串，表示目标状态 $target$。

输出格式

• 一个整数，表示最少旋转次数。如果无法解锁，则返回 -1。

3
8888
0001
9999 
0009

1

3 
0201 
0101 
0102 
0202

6

1
0101
0101

-1