752.打开转盘锁 (Medium)*
题目描述*
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
示例*
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，因为当拨动到 "0102" 时这个锁就会被锁定。
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：无法旋转到目标数字且不被锁定。
提示*
死亡列表 deadends 的长度范围为 [1, 500]。目标数字 target 不会在 deadends 之中。每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。
代码*
乍一看 8 太会，这个题是在 bfs 下遇到的，那就应该得用 bfs。
初始状态 0000，其相邻结点有 8 个，依次入队然后搜索，注意 deadends。
看题解里有带哥用双向 bfs，菜鸡第一次看到。维护两个队列，每次先从短的队列开始，使用一个公共的标志。
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
string start = "0000";
unordered_set<string> deadSet(deadends.begin(), deadends.end());
if(deadSet.count(start)) {
return -1;
}
queue<string> bfs;
unordered_set<string> visited{ start };
int steps = 0;
bfs.push(start);
while(!bfs.empty()) {
steps++;
int len = bfs.size();
for(int i = 0; i < len; i++) {
const string cur = bfs.front();
bfs.pop();
for(int j = 0; j < 4; j++) {
for(int step = -1; step <= 1; step += 2) {
string next = cur;
next[j] = (next[j] - '0' + step + 10) % 10 + '0';
if(next == target) {
return steps;
}
if(deadSet.count(next) || visited.count(next)) {
continue;
}
bfs.push(next);
visited.insert(next);
}
}
}
}
return -1;
}
};
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
const string start = "0000";
unordered_set<string> deadSet(deadends.begin(), deadends.end());
if(deadSet.count(start)) {
return -1;
}
queue<string> bfs;
queue<string> reBfs;
unordered_map<string, int> freqs;
int steps = 0;
bfs.push(start);
reBfs.push(target);
for(freqs[start] |= 1, freqs[target] |= 2; !bfs.empty() && !reBfs.empty(); steps++) {
bool sel = bfs.size() < reBfs.size();
queue<string> &q = (sel ? bfs : reBfs);
int mask = (sel ? 1 : 2);
int len = q.size();
for(int i = 0; i < len; i++) {
string cur = q.front();
q.pop();
if(freqs[cur] == 3) {
return steps;
}
for(int j = 0; j < 4; j++) {
for(int step = -1; step <= 1; step += 2) {
string next = cur;
next[j] = (next[j] - '0' + step + 10) % 10 + '0';
if(deadSet.count(next) || freqs[next] & mask) {
continue;
}
freqs[next] |= mask;
q.push(next);
}
}
}
}
return -1;
}
};