Description

Submission

class Solution {
    void prevStr(string& s, int i) {
        if(s[i] == '0') {
            s[i] = '9';
        } else {
            s[i] -= 1;
        }
    }

    void nextStr(string& s, int i) {
        if(s[i] == '9') {
            s[i] = '0';
        } else {
            s[i] += 1;
        }
    }
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> visited;

        for(auto& s: deadends) {
            visited.insert(s);
        }

        queue<string> q;
        q.push("0000");
        int ret = 0;

        for(; !q.empty(); ++ret) {
            int n = q.size();
            for(int i = 0; i < n; ++i) {
                string cur = q.front();
                q.pop();
                if(visited.count(cur)) continue;
                visited.insert(cur);

                if(cur == target) return ret;

                for(int i = 0; i < 4; ++i) {
                    prevStr(cur, i);
                    if(!visited.count(cur)) q.push(cur);
                    nextStr(cur, i);
                    nextStr(cur, i);
                    if(!visited.count(cur)) q.push(cur);
                    prevStr(cur, i);
                }
            }
        }

        return -1;
    }
};