【BFS】752. 打开转盘锁

752. 打开转盘锁

解题思路

• 密码。问题变成了在图中找到从起始密码到目标密码的最短路径。

• 状态表示： 使用字符串表示密码，每一位数字表示密码的一个位置。例如，“0000” 表示一个初始密码。

• 搜索过程： 使用广度优先搜索（BFS）来遍历图。从初始密码开始，通过向上或向下旋转某一位数字，生成相邻的密码。将未访问过的相邻密码加入队列，继续搜索。通过 BFS 的性质，一旦找到目标密码，即可确定为最短路径，因为首次遇到目标密码时，搜索过程已经遍历了所有可能的路径。

• 避免重复和死亡密码： 使用集合来记录已经访问过的密码，防止走回头路。同时，将不允许使用的死亡密码存储在一个集合中，确保搜索过程中跳过这些无效的密码。

• 步数计算： 通过 BFS 遍历的层数即为从起始密码到目标密码的最短路径长度，因为每一层表示通过一次旋转得到的新密码。

• 时间复杂度： BFS 算法的时间复杂度主要受到搜索过程中的节点数的影响，但由于每个密码有8个相邻的密码，所以搜索过程中的节点数相对有限，时间复杂度较为合理。

class Solution {
    // 向上旋转
    String plusOne(String s,int j){
        char[] ch = s.toCharArray();
        if(ch[j] == '9'){
            ch[j] = '0';
        }else{
            ch[j] += 1;
        }

        return new String(ch);
    }

    // 向下旋转
    String minusOne(String s,int j){
        char[] ch = s.toCharArray();
        if(ch[j] == '0'){
            ch[j] = '9';
        }else{
            ch[j] -= 1;
        }

        return new String(ch);
    }

    public int openLock(String[] deadends, String target) {
        // 每一个节点有八个节点 计算从根节点到达目标节点的最短距离

        // 0000为根节点  每一个节点向上或者向下寻转 然后有八种可能

        // 记录需要跳过的死亡密码
        Set<String> deads = new HashSet<>();
        for(String s:deadends){
            deads.add(s);
        }

        // 记录已经出现的密码 防止走回头路
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();

        // 从起点开始启动广度优先搜索 BFS
        int step = 0;
        q.offer("0000");// 根节点入队
        visited.add("0000");

        while(!q.isEmpty()){
            int sz = q.size();// 计算队列的长度

            for(int i = 0; i < sz; i++){
                String cur = q.poll();

                // 判断是不是根节点
                if(deads.contains(cur)){
                    continue;// 如果遇到死亡密码
                }

                if(cur.equals(target)){
                    // 遇到目标密码
                    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;
    }
}