72 lines
1.6 KiB
C++
72 lines
1.6 KiB
C++
#include <vector>
|
|
#include <unordered_set>
|
|
#include <string>
|
|
#include <queue>
|
|
#include <iostream>
|
|
|
|
class Solution {
|
|
public:
|
|
union u {
|
|
public:
|
|
char c[4];
|
|
int i;
|
|
};
|
|
|
|
int openLock(std::vector<std::string>& deadends, std::string target) {
|
|
std::unordered_set<int> e;
|
|
std::queue<std::pair<u,int>> q;
|
|
|
|
u t;
|
|
u b;
|
|
b.i = 0;
|
|
for (int i = 0; i < 4; ++i) {
|
|
t.c[i] = static_cast<char>(target[i] - '0');
|
|
}
|
|
for (const auto& i : deadends) {
|
|
if (target == i || i == "0000") return -1;
|
|
|
|
u tmp;
|
|
for (int j = 0; j < 4; ++j) {
|
|
tmp.c[j] = static_cast<char>(i[j] - '0');
|
|
}
|
|
e.insert(tmp.i);
|
|
}
|
|
|
|
|
|
|
|
e.insert(0);
|
|
q.emplace(b,0);
|
|
|
|
while(q.size()) {
|
|
auto i = q.front();
|
|
q.pop();
|
|
if (i.first.i == t.i) return i.second;
|
|
|
|
for (int j = 0; j < 4; ++j) {
|
|
u w = i.first;
|
|
++w.c[j] %= 10;
|
|
auto it = e.emplace(w.i);
|
|
if (it.second) {
|
|
q.emplace(w, i.second + 1);
|
|
}
|
|
}
|
|
|
|
for (int j = 0; j < 4; ++j) {
|
|
u w = i.first;
|
|
if (!w.c[j]--) w.c[j] = 9;
|
|
auto it = e.emplace(w.i);
|
|
if (it.second) {
|
|
q.emplace(w, i.second + 1);
|
|
}
|
|
}
|
|
}
|
|
return -1;
|
|
}
|
|
};
|
|
|
|
int main() {
|
|
Solution s;
|
|
std::vector<std::string> v = {"8888"};
|
|
std::cout << s.openLock(v, "0009");
|
|
return 0;
|
|
} |