剑指 Offer II 109. 开密码锁

 链接：剑指 Offer II 109. 开密码锁

题解：

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        std::unordered_set<std::string> table(deadends.begin(), deadends.end());
        // 面向异常设计
        if (table.find("0000") != table.end()) {
            return -1;
        }
        // 面向异常设计
        if (target == "0000") {
            return 0;
        }
        std::queue<std::pair<std::string, int>> que;
        que.push(make_pair("0000", 0));
        std::unordered_set<std::string> visited;
        visited.insert("0000");
        while (!que.empty()) {
            auto f = que.front();
            que.pop();
            for (auto& neighboard : get_neighboards(f.first)) {
                if (visited.find(neighboard) != visited.end() || table.find(neighboard) != table.end()) {
                    continue;
                }
                if (neighboard == target) {
                    return f.second+1;
                }
                que.push(std::make_pair(neighboard, f.second+1));
                visited.insert(neighboard);
            }
        }
        return -1;
    }
private:
    std::vector<std::string> get_neighboards(std::string& cur) {
        auto next = [](char a)->char {
            return a == '9' ? '0' : a+1;
        };
        auto prev = [](char a)->char {
            return a == '0' ? '9' : a-1;
        };
        std::vector<std::string> result;
        for (int i = 0; i < cur.size(); ++i) {
            char c = cur[i];
            cur[i] = next(c);
            result.push_back(cur);
            cur[i] = prev(c);
            result.push_back(cur);
            cur[i] = c;
        }
        return result;
    }
};