OPEN_THE_LOCK

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        set<int> s;
        for(auto it:deadends)
            s.insert(stoi(it));
        queue<pair<int,int>> q;
        q.push({0,0});
        vector<bool> vis(10000,false);
        vis[0] = true;
        while(!q.empty())
        {
            int v = q.front().first;
            int level = q.front().second;
            q.pop();

            if(s.count(v))
                continue;

            if(v==stoi(target)){
                return level;
            }

            string curr = "0000" + to_string(v);
            while(curr.length()>4)
                curr.erase(curr.begin());
            for(int j=0;j<4;j++){
                int num = curr[j]-'0';
                int next = num==9?0:num+1;
                int prev = num==0?9:num-1;
                string s1 = curr;
                string s2 = curr;
                s1[j] = '0' + next;
                s2[j] = '0' + prev;

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

        }

        return -1;
    }
};