leetcode 752. 打開轉盤鎖-BFS

解題思路：

• 由于題中所求的是需要撥動的次數，這裡可以優先考慮BFS，這是因為，每一次的狀态又8種，其中部分還是重複的，注意重複問題
• 注意死亡密碼問題

class Solution {
public:
    //向上撥動一次
    string plusOne(string s,int j){
        if(s[j] == '9'){
            //采用string位置替換函數
            s.replace(j,1,"0");
        }else{
            char temp = s[j];
            temp +=1;
            //string ms(1,char)是一種将char轉成string類型的ms方式
            s.replace(j,1,string(1,temp));
        }
        return s;
    }
    //向下撥動一次
    string minusOne(string s,int j){
        if(s[j] == '0'){
            //采用string位置替換函數
            s.replace(j,1,"9");
        }else{
            char temp = s[j];
            temp -=1;
            //string ms(1,char)是一種将char轉成string類型的ms方式
            s.replace(j,1,string(1,temp));
        }
        return s;
    }

    //主函數入口
    int openLock(vector<string>& deadends, string target) {
        //優先隊列儲存每一層中需要擴充的路徑
        queue<string> q;
        //記錄已經走過的路徑，防止走回頭路
        unordered_set<string> visited;
        //去重記錄需要跳過的死亡密碼
        unordered_set<string> deads;
        //将死亡密碼進行重新存儲，當set在find的時候會比vector要快
        for(string s : deadends){
            deads.insert(s);
        }
        //起點需要轉動的步數為0
        int step = 0;
        q.push("0000");
        visited.insert("0000");
        while(!q.empty()){
            int sz = q.size();
            for(int i = 0;i<sz;++i){
                string curr = q.front();
                q.pop();
                //判斷轉到死亡密碼位置，需要跳過
                if(deads.count(curr)){
                    continue;
                }
                //判斷轉到正确密碼位置，需要傳回步數
                if(curr == target){
                    return step;
                }
                //每次都可以轉動4個位置，每個位置可以向上轉動和向下轉動
                for(int j = 0;j<4;++j){
                    string up = plusOne(curr,j);
                    //判斷是否是已經走過的狀态
                    if(!visited.count(up)){
                        q.push(up);
                        visited.insert(up);
                    }
                    string down = minusOne(curr,j);
                    //判斷是否是已經走過的狀态
                    if(!visited.count(down)){
                        q.push(down);
                        visited.insert(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }
};