打开转盘锁

力扣 752. 打开转盘锁

题目说明

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

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

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

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
提示：
- 1 <= deadends.length <= 500
- deadends[i].length == 4
- target.length == 4
- target 不在 deadends 之中
- target 和 deadends[i] 仅由若干位数字组成

示例

示例 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:

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

笔者理解

此题是一道BFS算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题是比较有意思的一道BFS的题目，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * BFS
     * 经典层序遍历，类似于树的层序遍历原理，
     * 层序遍历当前步数之后的可能，加入队列中
     * 类似于树遍历中将孩子节点加入队列当中一样
     * 保证了层序的遍历顺序
     * 因为是先进先出的队列，所以保证只有遍历完一层之后才会遍历下一层
     */
    public int openLock(String[] deadends, String target) {
        // 目标就是原点，即无需步数
        if ("0000".equals(target)) {
            return 0;
        }

        // 存储死锁位置
        // 设为set方便查找
        Set<String> dead = new HashSet<String>();
        for (String deadend : deadends) {
            dead.add(deadend);
        }
        // 原点死锁，返回目标不可达
        if (dead.contains("0000")) {
            return -1;
        }

        // 计算步数
        int step = 0;

        // 此处使用LinkedList作为队列的实现
        Queue<String> queue = new LinkedList<String>();
        queue.offer("0000");

        // 标记已经走过的
        Set<String> seen = new HashSet<String>();
        seen.add("0000");

        while (!queue.isEmpty()) {
            ++step;
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                // 提取当前位置
                String status = queue.poll();

                for (String nextStatus : get(status)) {
                    // 如果当前位置没有走过而且不是死锁位置
                    if (!seen.contains(nextStatus) && !dead.contains(nextStatus)) {
                        if (nextStatus.equals(target)) {
                            return step;
                        }
                        queue.offer(nextStatus);
                        seen.add(nextStatus);
                    }
                }
            }
        }

        return -1;
    }

    // 数字向前转
    public char numPrev(char x) {
        return x == '0' ? '9' : (char) (x - 1);
    }

    // 数字向后转
    public char numSucc(char x) {
        return x == '9' ? '0' : (char) (x + 1);
    }

    // 枚举 status 通过一次旋转得到的数字
    public List<String> get(String status) {
        List<String> result = new ArrayList<String>();
        char[] array = status.toCharArray();
        for (int i = 0; i < 4; ++i) {
            char num = array[i];
            array[i] = numPrev(num);
            result.add(new String(array));
            array[i] = numSucc(num);
            result.add(new String(array));
            array[i] = num;
        }
        return result;
    }
}