752. Open the Lock

bfs O(Aⁿ) A是密码盘字母数，本题是10，n是密码盘个数，本题是4

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> cache(begin(deadends), end(deadends));
        if (cache.count("0000")) return -1;
        queue<string> q{{"0000"}};
        int res = 0;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto s = q.front(); q.pop();
                if (s == target) return res;
                for (auto &&c : s) {
                    auto t = c;
                    for (int i : {-1, 1}) {
                        c = '0' + (t - '0' + 10 + i) % 10;
                        if (!cache.count(s)) {
                            q.push(s);
                            cache.insert(s);
                        }
                    }
                    c = t;
                }
            }
            ++res;
        }
        return -1;
    }
};