题解 | #开锁#

import java.util.*;

/**
 * NC363 开锁
 * @author d3y1
 */
public class Solution {
    private HashSet<String> isForbidden;
    private HashSet<String> isVisited = new HashSet<>();
    private final int[] rotate = new int[]{1, -1};
    private final String START = "0000";
    private String TARGET;
    private int result = -1;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 程序入口
     *
     * @param vec string字符串ArrayList
     * @param tar string字符串
     * @return int整型
     */
    public int open (ArrayList<String> vec, String tar) {
        isForbidden = new HashSet<>(vec);
        TARGET = tar;
        
        bfs();

        return result;
    }

    /**
     * bfs
     * 等价于 图的最短路径
     */
    private void bfs(){
        Queue<String> queue = new LinkedList<>();
        queue.offer(START);
        isVisited.add(START);

        String curr;
        HashSet<String> nextSet;
        int level = -1;
        int size;
        while(!queue.isEmpty()){
            size = queue.size();
            level++;
            while(size-- > 0){
                curr = queue.poll();
                if(curr.equals(TARGET)){
                    result = level;
                    return;
                }
                // nextSet = nextCodes(curr);
                nextSet = nextCiphers(curr);
                for(String code: nextSet){
                    queue.offer(code);
                    isVisited.add(code);
                }
            }
        }
    }

    /**
     * 下一个密码
     * @param curr
     * @return
     */
    private HashSet<String> nextCodes(String curr){
        HashSet<String> nextSet = new HashSet<>();
        int digit,nextDigit;
        String code;
        for(int i = 0; i < 4; i++){
            digit = curr.charAt(i)-'0';
            for(int j = 0; j <= 1; j++){
                nextDigit = (digit+rotate[j]+10)%10;
                code = curr.substring(0, i) + nextDigit + curr.substring(i+1);
                if(!isForbidden.contains(code) && !isVisited.contains(code)){
                    nextSet.add(code);
                }
            }
        }

        return nextSet;
    }

    /**
     * 下一个密码
     * @param code
     * @return
     */
    private HashSet<String> nextCiphers(String code){
        HashSet<String> nextSet = new HashSet<>();
        String up,down;
        for(int i = 0; i < 4; i++){
            up = plusOne(code, i);
            if(!isForbidden.contains(up) && !isVisited.contains(up)){
                nextSet.add(up);
            }
            down = minusOne(code, i);
            if(!isForbidden.contains(down) && !isVisited.contains(down)){
                nextSet.add(down);
            }
        }

        return nextSet;
    }

    /**
     * 向上转一位
     * @param code
     * @param i
     * @return
     */
    private String plusOne(String code, int i){
        char[] chs = code.toCharArray();
        if(chs[i] == '9'){
            chs[i] = '0';
        }else{
            chs[i] += 1;
        }
        
        return new String(chs);
    }

    /**
     * 向下转一位
     * @param code
     * @param i
     * @return
     */
    private String minusOne(String code, int i){
        char[] chs = code.toCharArray();
        if(chs[i] == '0'){
            chs[i] = '9';
        }else{
            chs[i] -= 1;
        }
        
        return new String(chs);
    }
}