openlock BFS

openLock.cc

class Solution {
public:
    bool check_deadends(unordered_set<string>& deadends, const string & target){
        if(deadends.find(target) != deadends.end()) return true;
        deadends.insert(target);
        return false;
    }
    
    bool check_target(const string & a, const string & b){ 
        return (a==b);
    }
    
    string make_move(const string & a, const int & pos, const int & dir){
        string res = a;
        char val1 = res[pos]; 
        int val = val1 - '0' + dir;
        res[pos] = val+'0';
        if(val == 10) res[pos] ='0';
        if(val == -1) res[pos] ='9'; 
        return res;
    }
    
    bool visited(const string & a, unordered_set<string> & p){
        if(p.find(a) != p.end()) return true;
        return false;
    }
    void print(const vector<string> &a){
        for(const auto &it:a)
            cout<<it<<" ";
        cout<<endl;
    }
    
    int openLock(vector<string>& deadend, string target) {
        unordered_set<string>  deadends;
        for(const auto & it : deadend)
            deadends.insert(it);
        
        if (check_deadends(deadends, "0000"))
            return -1;
        
        queue<string> nex;
        nex.push("0000"); 
        int l = 0;
        unordered_set<string> path;
        while(nex.size()){ 
            int len = nex.size();
            l++;
            for(int i = 0; i<len; i++){
                string it = nex.front();
                nex.pop();
                for(int pos = 0; pos < 4; pos++){
                    for(int dir = 0; dir<2; dir++){
                        int dd = 1;
                        if(dir) dd = -1;
                        string mov = make_move(it, pos, dd); 
                        if(check_target(mov, target)) return l;
                        if(check_deadends(deadends, mov) == false 
                           && visited(mov, path) == false){
                            nex.push(mov);
                        }
                    }
                }
            }  
        }
        return -1;
    }
};