题目

https://leetcode.com/problems/open-the-lock/

题解

先写了个 DFS，超时了。

看了下 Related Topics，提示说应该是 BFS。这已经不是第一次遇到 BFS 可以、DFS 超时的题目了。

总结了一下，对于这种可以用 DFS/BFS 求最短路径的题目，优先选择 BFS，因为你到达目标的可能性有超级多种，而大多数路线都走了很多弯路，去遍历它们都是无用功。用 BFS 的话，从 step=1 开始逐渐递增，在 step 受限的情况下，只要到达了目标，当前 step 一定是最短的 step。

另外，本题可以使用 智能算法（只是想到了，没有尝试过）（遗传/蚁群） / 启发式搜索（答案提到了，例如 A*）来做，作为拓展思路，本文不作实现。

class Solution {
    public int openLock(String[] deadends, String target) {
        int t = Integer.parseInt(target);
        Set<Integer> block = new HashSet<>();
        for (String s : deadends) {
            block.add(Integer.parseInt(s));
        }

        Set<Integer> seen = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        int step = 0;
        while (!stack.isEmpty()) {
            Stack<Integer> nextStack = new Stack<>();
            while (!stack.isEmpty()) {
                int cur = stack.pop();
                if (cur == t) return step;
                if (block.contains(cur) || seen.contains(cur)) continue;
                seen.add(cur);
                nextStack.add(move(cur, 0, true));
                nextStack.add(move(cur, 0, false));
                nextStack.add(move(cur, 1, true));
                nextStack.add(move(cur, 1, false));
                nextStack.add(move(cur, 2, true));
                nextStack.add(move(cur, 2, false));
                nextStack.add(move(cur, 3, true));
                nextStack.add(move(cur, 3, false));
            }
            step++;
            stack = nextStack;
        }
        return -1;
    }

    public int move(int cur, int index, boolean front) {
        int[] arr = new int[4];
        int i = 3;
        while (cur != 0) {
            arr[i] = cur % 10;
            cur /= 10;
            i--;
        }

        arr[index] = front ? ((arr[index] + 1) + 10) % 10 : ((arr[index] - 1) + 10) % 10;

        int result = 0;
        for (int j = 0; j < 4; j++) {
            result *= 10;
            result += arr[j];
        }
        return result;
    }
}