1、前言

2、思路

主要思路使用 BFS。锁有四个位置，从 “0000” 开始，每个位置如果只转一下，分为向上转跟向下转，一共有8种选择。等于说一个节点连着8个节点，所有都可以组成一张图。但是肯定有重复的，所以需要记录重复的。

3、代码

public class OpenRotateLock {


    public int openLock(String[] deadends, String target) {

        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        Set<String> dead = new HashSet<>();

        for (String deadend : deadends) {
            dead.add(deadend);
        }

        queue.offer("0000");
        visited.add("0000");

        int step = 0;

        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String current = queue.poll();

                if(dead.contains(current)){
                    continue;
                }

                if(current.equals(target)){
                    return step;
                }

                List<String> neibors = rotate(current);
                for (String neibor : neibors) {
                    if(!visited.contains(neibor)){
                        visited.add(neibor);
                        queue.offer(neibor);
                    }
                }
            }

            step++;
        }

        return -1;
    }

    private List<String> rotate(String current) {
        List<String> res = new ArrayList<>();
        for(int i = 0; i < current.length(); i++){
            res.add(lockUP(current.toCharArray(), i));
            res.add((lockDown(current.toCharArray(), i)));
        }
        return res;
    }

    private String lockUP(char[] chars, int index){
        if(chars[index] == '9'){
            chars[index] = '0';
        } else {
            chars[index]++;
        }

        return new String(chars);
    }

    private String lockDown(char[] chars, int index){
        if(chars[index] == '0'){
            chars[index] = '9';
        } else {
            chars[index]--;
        }

        return new String(chars);
    }


    public static void main(String[] args) {
        String[] deadends = {"0201","0101","0102","1212","2002"};
        String target = "0202";

        System.out.println(new OpenRotateLock().openLock(deadends, target));
    }
}