752. Open the Lock

這題也很好玩, 用bfs, 要注意鎖可以往上轉也可以往下轉,

如果這個數字做過就用table記一下吧, 以免浪費多餘的時間在上面

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        queue<string> q;
        q.push("0000");
        unordered_set<string> st(deadends.begin(), deadends.end());
        unordered_set<string> visited;
        int res = 0;
        while(!q.empty()){
            int len = q.size();
            for(int i = 0;i<len;i++){
                string cur = q.front();
                q.pop();
                if(st.count(cur)){
                    continue;
                }
                if(cur == target) return res;
                for(int j = 0; j < cur.size();j++){
                    string tmp1 = cur;
                    string tmp2 = cur;
                    tmp1[j] = tmp1[j] == '9'? '0': tmp1[j] + 1;
                    tmp2[j] = tmp2[j] == '0'? '9': tmp2[j] - 1;
                    
                    if(!visited.count(tmp1)){
                        q.push(tmp1);
                        visited.insert(tmp1);
                    }
                    if(!visited.count(tmp2)){
                        q.push(tmp2);
                        visited.insert(tmp2);
                    } 
                }
            }
            res++;
        }
        return -1;
    }
};