题解 | #开锁#

BFS算法

import java.util.*;
public class Solution {
    public int open (ArrayList<String> vec, String tar) {
        //记录非法密码
        Set<String> deadPassword = new HashSet<>();
        for(String s:vec){
            deadPassword.add(s);
        }
        //记录已经穷举过的密码，防止重复
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        q.offer("0000");
        int step = 0;
        visited.add("0000");
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i<size;i++){
                String cur = q.poll();
                if(deadPassword.contains(cur)){
                    continue;
                }
                if(cur.equals(tar)){
                    return step;
                }
                for(int j = 0;j<4;j++){
                    String up = plusOne(cur,j);
                    if(!visited.contains(up)){
                        q.offer(up);
                        visited.add(up);
                    }
                    String down = minusOne(cur,j);
                    if(!visited.contains(down)){
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }
    //向上拨动一位
    private String plusOne(String s,int i){
        char[] ch = s.toCharArray();
        if(ch[i] == '9'){
            ch[i] = '0';
        }else{
            ch[i] += 1;
        }
        return new String(ch);
    }
    //向下拨动一位
    private String minusOne(String s,int i){
        char[] ch = s.toCharArray();
        if(ch[i] == '0'){
            ch[i] = '9';
        }else{
            ch[i] -= 1;
        }
        return new String(ch);
    }
}