752. 打开转盘锁

知识点：图；BFS

题目描述

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

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

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

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

示例

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

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

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

输入: deadends = ["0000"], target = "8888"
输出：-1

---

解法一：BFS

这道题目看起来很绕，其实透过这个场景去看本质，其实就是一幅图，什么意思呢，每个密码就可以看做是图的节点，目标就是找到target的节点，怎么办，遍历呗，啥时候找到啥时候停，而图的遍历自然要用到BFS，每个节点其实都有8个相邻节点，因为它转动后下一个可能的密码就是8个，举个例子，比如"0000"转一下以后"1000,9000,0100,0900,..."，这就是相邻节点；然后还有用一个visited来记录已经遍历过的，防止回头路，此外如果有密码等于deadend了，那就跳过不用遍历这个密码了。

BFS算法框架：

//计算起点start到终点target的最小距离
int BDS(Node start, Node target){ 
    Queue<Node> queue;  //核心结构：队列；
    Set<Node> visited;  //在图中都会用到，因为存在着交叉，会走回头路，树中则不需要，因为有next指针；
    queue.offer(start);  //起点入队；
    visited.add(start);  
    int step = 0; //记录扩散步数；
    while(queue.isEmpty()){
        int size = queue.size();
        //从当前队列中所有节点向与其关联的节点扩散；
        for(int i = 0; i < size; i++){
            Node cur = queue.poll();
            if(cur == target){
                return step;  //注意不同题目里这里的判断条件，是否到达终点；
            }
            for(Node x : cur.adj()){  //这里指的是当前节点的邻居节点；
                if(!visited.contains(x)){ //还没走过再加入；不走回头路；
                    queue.offer(x);
                    visited.add(x);
                }
            }
        }
        step++;  //注意在这里更新步数；
    }
}

题解：

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<>();
        for(String s:deadends){
            dead.add(s);
        }
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        Set<String> visited = new HashSet<>();
        visited.add("0000");  //记录所有已经遍历到的密码；
        int step = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                String cur = queue.poll();
                //截止条件；
                if(dead.contains(cur)) continue;
                if(cur.equals(target)) return step;
                //处理相邻节点；一共8个；
                for(int j = 0; j < 4; j++){
                    String up = plusOne(cur, j);
                    if(!visited.contains(up)){
                        visited.add(up);
                        queue.offer(up);
                    }
                    String down = minusOne(cur, j);
                    if(!visited.contains(down)){
                        visited.add(down);
                        queue.offer(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }
    private String plusOne(String s, int j){
        char[] ch = s.toCharArray();
        if(ch[j] == '9') ch[j] = '0';
        else ch[j] += 1;
        return new String(ch);
    }
    private String minusOne(String s, int j){
        char[] ch = s.toCharArray();
        if(ch[j] == '0') ch[j] = '9';
        else ch[j] -= 1;
        return new String(ch);
    }
}

仔细看一下上述题解，基本上是和框架也就是模板是一样的，要注意灵活变通。