BFS最短路模型
状态之间转换的最短路模型。
把每个状态看成一个点,看成从某个点开始BFS搜索其他状态。
最终目标状态被转移到就是最短的操作次数。
- 将初始状态入队
-
BFS过程
-
对于该状态来说,枚举该状态能转移到的状态
- 若转移到的状态没在黑名单,并且没被搜索到过,则转移到的状态步数=该状态步数+1,并且入队
AC代码
class Solution {
public:
unordered_set<string> deads;
unordered_map<string,int> dis;
//s[i] + 1
string add(string s, int i) {
s[i] ++;
if (s[i] > '9') s[i] = '0';
return s;
}
//s[i] - 1
string sub(string s, int i) {
s[i] --;
if (s[i] < '0') s[i] = '9';
return s;
}
int bfs(string start, string& end){
queue<string> q;
q.push(start);
dis[start] = 0;
//特判初始状态在黑名单
if (deads.count(start))
return -1;
while (q.size()) {
auto t = q.front();
q.pop();
if (t == end) return dis[end];
//枚举所有能转移的状态
for (int i = 0 ; i < 4 ; i ++) {
string s1 = add(t, i);
string s2 = sub(t, i);
if (!deads.count(s1) && !dis.count(s1)){
q.push(s1);
dis[s1] = dis[t] + 1;
}
if (!deads.count(s2) && !dis.count(s2)){
q.push(s2);
dis[s2] = dis[t] + 1;
}
}
}
return -1;
}
int openLock(vector<string>& deadends, string target) {
//黑名单插入哈希表
for (auto& s : deadends)
deads.insert(s);
//BFS
int res = bfs("0000", target);
return res;
}
};