1、題目

image.png

2、分析

基本上直接套用BFS的算法框架就可以

// 計算從起點(diǎn) start 到終點(diǎn) target 的最近距離
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心數(shù)據(jù)結(jié)構(gòu)
    Set<Node> visited; // 避免走回頭路
    
    q.offer(start); // 將起點(diǎn)加入隊列
    visited.add(start);
    int step = 0; // 記錄擴(kuò)散的步數(shù)

    while (q not empty) {
        int sz = q.size();
        /* 將當(dāng)前隊列中的所有節(jié)點(diǎn)向四周擴(kuò)散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 劃重點(diǎn)：這里判斷是否到達(dá)終點(diǎn) */
            if (cur is target)
                return step;
            /* 將 cur 的下一步要都加入隊列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 劃重點(diǎn)：更新步數(shù)在這里 */
        step++;
    }
}

3攻人、代碼

class Solution {
    //某個輪盤加一
    public String up(String s, int i){
        char[] ch = s.toCharArray();
        if(ch[i] == '9'){
            ch[i] = '0';
        }
        else{
            ch[i] += 1;
        }
        return new String(ch);
    }
    //某個輪盤減一
    public String down(String s, int i){
        char[] ch = s.toCharArray();
        if(ch[i] == '0'){
            ch[i] = '9';
        }
        else{
            ch[i] -= 1;
        }
        return new String(ch);
    }

    public int openLock(String[] deadends, String target) {
        //隊列
        Queue<String> queue = new LinkedList<>();
        //存儲已經(jīng)走過的節(jié)點(diǎn)颈走，防止走回頭路
        Set<String> visited = new HashSet<>();
        Set<String> deadSet = new HashSet<>();
        for(String s : deadends) deadSet.add(s);
        queue.offer("0000");
        visited.add("0000");
        int times = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            //遍歷這一步所有的結(jié)果
            for(int i = 0; i < size; i++){
                String cur = queue.poll();
                //找到結(jié)果敞峭，或者包含在死鎖中
                if(deadSet.contains(cur)) continue;
                if(cur.equals(target)) return times;
                //某一個結(jié)果攻柠，下一步有哪幾種可能都列出來球订，加到隊列中
                for(int j = 0; j < 4; j++){
                    String up = up(cur, j);
                    if(!visited.contains(up)){
                        queue.offer(up);
                        visited.add(up);
                    }
                    String down = down(cur, j);
                    if(!visited.contains(down)){
                        queue.offer(down);
                        visited.add(down);
                    }
                }
            }
            //步數(shù)加一
            times++;
        }
        return -1;
    }
}