打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以*旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

示例 1:
输入：deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202”
输出：6
解释：
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的，
因为当拨动到 “0102” 时这个锁就会被锁定。

示例 2:
输入: deadends = [“8888”], target = “0009”
输出：1
解释：
把最后一位反向旋转一次即可 “0000” -> “0009”。

示例 3:
输入: deadends = [“8887”,“8889”,“8878”,“8898”,“8788”,“8988”,“7888”,“9888”], target = “8888”
输出：-1
解释：
无法旋转到目标数字且不被锁定。

示例 4:
输入: deadends = [“0000”], target = “8888”
输出：-1

提示：
1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target 不在 deadends 之中
target 和 deadends[i] 仅由若干位数字组成

广度优先搜索的空间图

while循环的每次循环遍历其中一层

如果想打印路径的话可以用链表节点，每个状态的上一步状态作为父节点。节点结构为指向父节点的指针和字符串（或数字）

一边BFS一边构建出一颗由子节点指向父结点的树，队列中保存着叶子节点。当访问到了target。可以递归打印整个路径

	public int openLock(String[] deadends, String target) {

        if(target.equals("0000") ){       //答案就是初始状态，需要拨动零次，返回0
            return 0;
        }

        int step = 0;   //记录拨动次数
        Set<String> deads = new HashSet();  //deadend放到hashset,方便判断当前状态是否为deadend,不然要遍历

        for (String deadend : deadends) {   //deadend放到hashset
            deads.add(deadend);
        }

        if(deads.contains("0000")){     //deadend中有初始状态的话说明无法旋转到目标数字且不被锁定。返回-1；
            return -1;
        }

        Queue<String> queue = new LinkedList<>();   //创建队列，并将初始状态入队
        queue.offer("0000");

        Set<String> tried = new HashSet<>();    //创建一个hashSet来存储已经尝试过的密码
        tried.add("0000");

        while (!queue.isEmpty()){
            //  队中的是上一次循环已经访问过的所有状态，每次循环，判断这些状态的相邻状态是否有为target，
            // 有的话返回step,不是的话把相邻状态添加到队列。（前提是相邻状态还没进队列）
            ++step;
            int size = queue.size();    //要先把队列长度保存下来，不能在for中直接用queue.size（）,因为队列长度会变化

            for (int i = 0; i < size ; i++) {
                String status = queue.poll();

                for ( String neighbor : getNeighbors(status)) {
                    if(!tried.contains(neighbor) && !deads.contains(neighbor)){

                        if(neighbor.equals(target)){    //如果扭到target了，返回step
                            return step;
                        }
                        queue.offer(neighbor);
                        tried.add(neighbor);
                    }
                }  //for ( String neighbor : getNeighbors(status))
            }//for (int i = 0; i < size ; i++)
        }//while (!queue.isEmpty())

        //循环结束，说明所有可能都遍历了，并且没有得到target,说明无法旋转到目标数字且不被锁定。返回-1；
        return -1;
    }

    char goAhead(char c){
        return c == '0' ? '9' : (char)(c - 1);   //向前拨动数字
    }

    char goBack(char c){
        return c == '9' ? '0' : (char) (c + 1);     //向后拨动数字
    }

    List<String> getNeighbors(String str){      //获取当前状态的八个相邻状态
        char[] arr = str.toCharArray();
        List<String> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {  //一共四位，每一位有前后两个邻居，轮流获取相邻状态

            char letter = arr[i];       //获取当前位

            arr[i] = goAhead(letter);       //将前后两个相邻状态加入列表
            list.add(new String(arr));

            arr[i] = goBack(letter);
            list.add(new String(arr));

            arr[i] = letter;        //复原当前位
        }
        return list;
    }