package 宽度优先搜索;

import java.util.*;

public class Code_bfs2打开转盘锁 {
    public static int bfs(String target, String[] deadends) {
        Queue<String> q = new LinkedList<String>();
        Set<String> set = new HashSet<String>();
        List<String> list = Arrays.asList(deadends);  // 转到这个数组中的任何数都会被锁死
        String start = "0000";
        int step = 0;
        if(start.equals(target)) {  // 字符串比较时还是要用 equals
            return step;
        }
        if(list.contains(target)) {
            return -1;
        }
        q.offer(start);
        set.add("0000");
        while(!q.isEmpty()) {
            step++; // 注意这个step的位置
            int size = q.size();
            for(int i = 0; i < size; i++) {
                String now = q.peek();
                if(now.equals(target)) {
                    return step;
                }
                String[] neibor = getNeibor(now);
                for(String nei : neibor) {
                    if(set.contains(nei) == false && list.contains(nei) == false) {
                        q.offer(nei);
                        set.add(nei);
                    }
                }
                if(q.contains(target)) {  // 看在这一次的搜索中有没有target
                    return step;
                }
                q.poll();
            }
            
        }
        return -1;
    }
    
    private static String[] getNeibor(String now) {
        String[] res = new String[8]; // 因为这个转盘每一次只能转一次所以我们对每一个扭 +1或者-1
        for(int i = 0; i < 4; i++) {
            char[] ch = now.toCharArray();  // 将now的每一位拨动
            int a = ch[i] - '0';  // 当这个位置上是0时减1就会变成9
            if(a == 0) {
                ch[i] = '9';
            }else {
                ch[i] = Character.forDigit(a - 1, 10); // forDigit 将a-1表示成10进制的chara
            }
            res[2 * i] = String.valueOf(ch);
            if(a == 9) {
                ch[i] = '0';
            }else {
                ch[i] = Character.forDigit(a + 1, 10);
            }
            res[2 * i + 1] = String.valueOf(ch);
        }
        return res;
    }
    public static void main(String[] args) {
        String[] d = {"0201", "0000"};
        System.out.println(bfs("8888", d));
    }
}