752

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        vector<bool> vis(10000, false);
        for(string &str: deadends)
            vis[stoi(str)] = true;

        queue<string> q;
        string start = "0000";
        if(!vis[stoi(start)]){
            q.push(start);
            vis[stoi(start)] = true;
        }

        int steps = 0;
        if(start == target) return steps;
        while(!q.empty()){
            int sz = q.size();
            for(int i=0; i<sz; i++){
                string current = q.front();
                q.pop();

                for(int i=0; i<4; i++){
                    string next = current;
                    next[i] = ((next[i]-'0')+1)%10 + '0';
                    if(!vis[stoi(next)]){
                        q.push(next);
                        vis[stoi(next)] = true;
                        if(next == target)
                            return steps+1;
                    }
                    next = current;
                    next[i] = ((next[i]-'0')-1+10)%10 + '0';
                    if(!vis[stoi(next)]){
                        q.push(next);
                        vis[stoi(next)] = true;
                        if(next == target)
                            return steps+1;
                    }
                }
            }
            steps++;
        }
        return -1;
    }
};