你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以*旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
方法一：BFS，注意转动范围，0和9要特殊考虑，首先考虑0000就是答案，直接返回0，第一次剪枝，再考虑0000无法访问，第二次剪枝然后用visited记录访问过的，第三次剪枝
class Solution {
public int openLock(String[] deadends, String target) {
if(target.equals("0000"))return 0;
Deque<String>queue=new LinkedList<>();
HashSet<String>dead=new HashSet<>();
for(int i=0;i<deadends.length;i++){
if("0000".equals(deadends[i])){
return -1;
}
dead.add(deadends[i]);
}
HashSet<String>visited=new HashSet<>();
int res=0;
queue.offer("0000");
visited.add("0000");
while(!queue.isEmpty()){
res++;
int size=queue.size();
for(int i=0;i<size;i++){
String s=queue.poll();
List<String>status=change(s, visited);
for(String str:status){
if(dead.contains(str))continue;
if(str.equals(target))return res;
queue.offer(str);
visited.add(str);
}
}
}
return -1;
}
List<String>change(String s,HashSet<String>visited){
List<String>res=new ArrayList<>();
char[] arr = s.toCharArray();
for(int i=0;i<4;i++){
char c=arr[i];
arr[i]=nextNum(c);
String str1=new String(arr);
if(!visited.contains(str1)){
res.add(str1);
}
arr[i]=lastNum(c);
String str2=new String(arr);
if(!visited.contains(str2)){
res.add(str2);
}
//一定要复原(回溯)
arr[i]=c;
}
return res;
}
public char lastNum(char x) {
return x == '0' ? '9' : (char) (x - 1);
}
public char nextNum(char x) {
return x == '9' ? '0' : (char) (x + 1);
}
}