[LeetCode] 752. Open the Lock

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.

Example 4:

Input: deadends = ["0000"], target = "8888"
Output: -1

Constraints:

1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target will not be in the list deadends.
target and deadends[i] consist of digits only.

题解双向 BFS

类似题：LeetCode 127 Word Ladder II

看到有 deadends 其实就比较明显了——这是个走迷宫问题，而且因为有四位密码，所以其实是个四维迷宫。维数并不会增加解法的复杂程度，倒是会严重增加敲代码的繁琐程度。一开始是打算真的和迷宫一样，用四维数组做的，后来发现参数实在太多了，光敲一个位置就要 mem[i0][i1][i2][i3] 这样来一遍，实在有点头皮发麻，改用 String 和 Map 来做记忆化了。

还是当作迷宫来解，因此思想是 BFS ，因为入口和出口都是唯一确定的，前后都可以作为 BFS 的起点，因此可以通过双向 BFS 来收缩搜索范围。

首先把 deadends 存到一个 HashSet 里，方便查验。BFS 需要前后两个队列，分别维护一个记忆化搜索表，记录到 key 位置的步长。

 Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
d1.addLast(s);
m1.put(s, 0);
d2.addLast(t);
m2.put(t, 0);

然后就是 BFS 了，一直搜到队列空为止。为了尽量收缩双向 BFS 的搜索范围，每次从更小的队列取元素进行搜索。

while (!d1.isEmpty() && !d2.isEmpty()) {
    int t = -1;
    if (d1.size() <= d2.size()) {
        t = update(d1, m1, m2);
    } else {
        t = update(d2, m2, m1);
    }
    if (t != -1) return t;
}

每次搜索要搜相邻的八个位置，也就是每一位的前后两个数字。原数字是 char[i] 的话，以十为模加一或加九就行了——(char) ('0' + ((chars[i] - '0' + offset) % 10)) 。

新状态的检查包括这样一些原则——

新位置不能是 deadend
新位置不能已经去过（在同一队列中），同一队列两次经过同一位置步长一定不会变短，也就不需要考虑了
在满足前两个前提下，如果能在反向记忆中找到相同状态，那一定是最短路径，直接输出
不在反向记忆中，就加入到当前记忆队列中，从而引起下一轮 BFS

char ori = chars[i];
chars[i] = (char) ('0' + ((chars[i] - '0' + offset) % 10));
String go = String.valueOf(chars);
chars[i] = ori;

if (this.deadEnds.contains(go))
    continue;
if (fs_map.containsKey(go))
    continue;
if (ot_map.containsKey(go)) {
    this.res = step + 1 + ot_map.get(go);
    return true;
}
fs_map.put(go, step + 1);
fs.addLast(go);

完整代码

int res;
int[] offset = {1, 9};
Set<String> deadEnds;
public int openLock_remastered(String[] dead, String target) {
    if (target.equals("0000"))
        return 0;
    this.deadEnds = new HashSet<>();
    // 虽然这里 IDE 会推荐让 Arrays 来把 String[] 转换成 Collection,但这样做对速度没有好处。
    // IDE 上测出来差别不大，但到了 LeetCode 上居然能让整题多耗将近一倍时间，百思不得其解。
    for (String str: dead)
        deadEnds.add(str);
    if (deadEnds.contains("0000"))
        return -1;
    Deque<String> front = new ArrayDeque<>();
    Map<String, Integer> front_map = new HashMap<>();
    Deque<String> back = new ArrayDeque<>();
    Map<String, Integer> back_map = new HashMap<>();
    front.addLast("0000");
    front_map.put("0000", 0);
    back.addLast(target);
    back_map.put(target, 0);
    while (!front.isEmpty() && !back.isEmpty()) {
        if (front.size() < back.size()) {
            if (update(front, front_map, back_map))
                return this.res;
        } else {
            if (update(back, back_map, front_map))
                return this.res;
        }
    }
    return -1;
}
private boolean update(Deque<String> fs, Map<String, Integer> fs_map, Map<String, Integer> ot_map) {
    String cur = fs.pollFirst();
    char[] chars = cur.toCharArray();
    int step = fs_map.get(cur);
    for (int i = 0; i < 4; ++i) {
        for (int offset : this.offset) {
            char ori = chars[i];
            // 在原 char[] 上改了，取完 String 再转回去，
            // 会比 clone() 新的要快很多
					 chars[i] = (char) ('0' + ((chars[i] - '0' + offset) % 10));
					 String go = String.valueOf(chars);
					 chars[i] = ori;	
          
            if (this.deadEnds.contains(go))
                continue;
            if (fs_map.containsKey(go))
                continue;
            if (ot_map.containsKey(go)) {
                this.res = step + 1 + ot_map.get(go);
                return true;
            }
            fs_map.put(go, step + 1);
            fs.addLast(go);
        }
    }
    return false;
}

题解 AStar 算法

作者：AC_OIer 链接：https://leetcode-cn.com/problems/open-the-lock/solution/gong-shui-san-xie-yi-ti-shuang-jie-shuan-wyr9/

可以直接根据本题规则来设计 A* 的「启发式函数」。

比如对于两个状态 a 和 b 可直接计算出「理论最小转换次数」：不同字符的转换成本之和。

需要注意的是：由于我们衡量某个字符 str 的估值是以目标字符串 target 为基准，因此我们只能确保 target 出队时为「距离最短」，而不能确保中间节点出队时「距离最短」，因此我们不能单纯根据某个节点是否「曾经入队」而决定是否入队，还要结合当前节点的「最小距离」是否被更新而决定是否入队。

这一点十分关键，在代码层面上体现在 map.get(str).step > poll.step + 1 的判断上。

注意：本题用 A* 过了，但通常我们需要先「确保有解」，A* 的启发搜索才会发挥真正价值。而本题，除非 t 本身在 deadends 中，其余情况我们无法很好提前判断「是否有解」。对于无解的情况 A* 效果不如「双向 BFS」。

源码

class Solution {
    class Node {
        String str;
        int val, step;
       /**
        *  str : 对应字符串
        *  val : 估值（与目标字符串 target 的最小转换成本）
        *  step: 对应字符串是经过多少步转换而来
        */
        Node(String _str, int _val, int _step) {
            str = _str;
            val = _val;
            step = _step;
        }
    }
    int f(String str) {
        int ans = 0;
        for (int i = 0; i < 4; i++) {
            int cur = str.charAt(i) - '0', target = t.charAt(i) - '0';
            int a = Math.min(cur, target), b = Math.max(cur, target);
            // 在「正向转」和「反向转」之间取 min
            int min = Math.min(b - a, a + 10 - b);
            ans += min;
        }
        return ans;
    }
    String s, t;
    Set<String> set = new HashSet<>();
    public int openLock(String[] ds, String _t) {
        s = "0000";
        t = _t;
        if (s.equals(t)) return 0;
        for (String d : ds) set.add(d);
        if (set.contains(s)) return -1;
        
        PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.val-b.val);
        Map<String, Node> map = new HashMap<>();
        Node root = new Node(s, f(s), 0);
        q.add(root);
        map.put(s, root);
        while (!q.isEmpty()) {
            Node poll = q.poll();
            char[] pcs = poll.str.toCharArray();
            int step = poll.step;
            if (poll.str.equals(t)) return step;
            for (int i = 0; i < 4; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (j == 0) continue;
                    int cur = pcs[i] - '0';
                    int next = (cur + j) % 10;
                    if (next == -1) next = 9;

                    char[] clone = pcs.clone();
                    clone[i] = (char)(next + '0');
                    String str = String.valueOf(clone);

                    if (set.contains(str)) continue;
                    // 如果 str 还没搜索过，或者 str 的「最短距离」被更新，则入队
                    if (!map.containsKey(str) || map.get(str).step > step + 1) {
                        Node node = new Node(str, step + 1 + f(str), step + 1);
                        map.put(str, node);
                        q.add(node);
                    }
                }
            }
        }
        return -1;
    }
}

LeetCode 752 - 打开转盘锁

双向BFS迷宫遍历.

[LeetCode] 752. Open the Lock

题解双向 BFS

题解 AStar 算法

[LeetCode] 752. Open the Lock

题解 双向 BFS

题解 AStar 算法

题解双向 BFS