752. 打开转盘锁

链接：

752. 打开转盘锁

题解：

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()|| table.find(target) != table.end()) {return -1;}std::queue<std::string> que;std::unordered_map<std::string, int> distance;que.push(std::string("0000"));distance["0000"] = 0;auto get_next = [](std::string& word)->std::vector<std::string> {std::vector<std::string> result;for (int i = 0; i < word.size(); ++i) {char ch = word[i];if (word[i] == '9') {word[i] = '0';} else {++word[i];}result.push_back(word);word[i] = ch;if (word[i] == '0') {word[i] = '9';} else {--word[i];}result.push_back(word);word[i] = ch;}return result;};while (!que.empty()) {int size = que.size();for (int i = 0; i < size; ++i) {auto f = que.front();que.pop();if (f == target) {return distance[f];}for (auto& next : get_next(f)) {//cout << "next = " << next << endl;if (table.find(next) != table.end()) {continue;}if (distance.find(next) != distance.end()) {continue;}/*if (next == target) {return distance[f] + 1;}*/distance[next] = distance[f] + 1;que.push(next);}}}return -1;}
};

class Solution {
public:int openLock(vector<string>& deadends, string target) {if (target == "0000") {return 0;}unordered_set<string> dead(deadends.begin(), deadends.end());if (dead.count("0000")) {return -1;}auto num_prev = [](char x) -> char {return (x == '0' ? '9' : x - 1);};auto num_succ = [](char x) -> char {return (x == '9' ? '0' : x + 1);};// 枚举 status 通过一次旋转得到的数字auto get = [&](string& status) -> vector<string> {vector<string> ret;string bak = status;for (int i = 0; i < 4; ++i) {char num = status[i];status[i] = num_prev(num);ret.push_back(status);status[i] = num_succ(num);ret.push_back(status);status = bak;}return ret;};queue<pair<string, int>> q;q.emplace("0000", 0);unordered_set<string> seen = {"0000"};int step = 0;while (!q.empty()) {auto [status, step] = q.front();q.pop();for (auto&& next_status: get(status)) {if (!seen.count(next_status) && !dead.count(next_status)) {if (next_status == target) {//return step + 1;return step+1;}q.emplace(next_status, step + 1);seen.insert(move(next_status));}}++step;}return -1;}
};