【双向BFS】打开转盘锁
2026-05-05 10:37:10
发布于：浙江
5阅读
0回复
0点赞
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int main(){
string e;
unordered_set<string> dead;
cin>>e;
string w;
while(cin>>w) dead.insert(w);
if(dead.count(e)){
cout<<-1;
return 0;
}
if("0000"==e){
cout<<0;
return 0;
}
queue<string> q;
unordered_map<string,int> dist;
q.push("0000");
dist["0000"]=0;
while(!q.empty()){
string cur=q.front();
q.pop();
int step=dist[cur];
if(cur==e){
cout<<step;
return 0;
}
for(int i=0;i<4;++i){
int d=cur[i]-'0';
string nxt=cur;
nxt[i]=(d+1)%10+'0';
if(!dead.count(nxt)&&!dist.count(nxt)){
dist[nxt]=step+1;
q.push(nxt);
}
nxt=cur;
nxt[i]=(d+9)%10+'0';
if(!dead.count(nxt)&&!dist.count(nxt)){
dist[nxt]=step+1;
q.push(nxt);
}
}
}
cout<<-1;
return 0;
}
这里空空如也
有帮助，赞一个