讨论/《广度优先搜索》 - 练习:打开转盘锁/
《广度优先搜索》 - 练习:打开转盘锁
共 1 个回复
    List<Integer> numList = Arrays.asList(1, 10, 100, 1000);

    public int openLock(String[] deadends, String target) {
        Set<Integer> dead = Arrays.stream(deadends).map(Integer::parseInt).collect(Collectors.toSet());
        Integer start = 0;
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited.add(start);
        int result = Integer.parseInt(target);
        if (start == result) {
            return 0;
        }
        if (dead.contains(0)) {
            return -1;
        }
        int step = 0;
        while (!queue.isEmpty()) {
            step++;
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                int curr = queue.poll();
                for (int num : numList) {
                    //加法 数字转换
                    int next = curr / num % 10 == 9 ? curr - num * 9 : curr + num;
                    if (next == result) {
                        return step;
                    }
                    if (!visited.contains(next) && !dead.contains(next)) {
                        visited.add(next);
                        queue.offer(next);
                    }
                    //减法 数字转换
                    next = curr / num % 10 == 0 ? curr + num * 9 : curr - num;
                    if (next == result) {
                        return step;
                    }
                    if (!visited.contains(next) && !dead.contains(next)) {
                        visited.add(next);
                        queue.offer(next);
                    }
                }
            }
        }

        return -1;
    }