OPEN_THE_LOCK_MINE

class Solution {

public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> s;
        for(auto it:deadends)
            s.insert(it);

        queue<pair<string,int>> q;
        q.push({"0000",0});

        unordered_map<string,bool> vis;
        // vector<bool> vis(10000,false);
        vis["0000"] = true;
        while(!q.empty())
        {
            string v = q.front().first;
            int level = q.front().second;
            q.pop();

            if(s.count(v))
                continue;

            if(v == target){
                return level;
            }
            for(int j=0;j<4;j++){
                int num = v[j]-'0';
                int next = num==9?0:num+1;
                int prev = num==0?9:num-1;
                string s1 = v;
                string s2 = v;
                s1[j] = '0' + next;
                s2[j] = '0' + prev;

                if(!vis[(s1)]){
                    vis[(s1)]=true;
                    q.push({(s1),level+1});
                }
                if(!vis[(s2)]){
                    vis[(s2)]=true;
                    q.push({(s2),level+1});
                }
            }

        }

        return -1;
    }
};