【双向BFS】单词接龙
2026-05-05 10:08:06
发布于：浙江
21阅读
0回复
0点赞
#include<bits/stdc++.h>
#include <unordered_set>
using namespace std;
int bdbfs(string &b,string &e,unordered_set<string> &dict){
if(!dict.count(e)) return 0;
if(b==e) return 1;
queue<string> q1,q2;
unordered_map<string,int> d1,d2;
q1.push(b);
q2.push(e);
d1[b]=1;
d2[e]=1;
while(!q1.empty()&&!q2.empty()){
if(q1.size()<=q2.size()){
int sz=q1.size();
for(int i=0;i<sz;i++){
string cur=q1.front();
q1.pop();
int step=d1[cur];
for(int p=0;p<cur.size();p++){
char old=cur[p];
for(char c='a';c<='z';c++){
if(c==old) continue;
cur[p]=c;
if(!dict.count(cur)) continue;
if(d1.count(cur)) continue;
if(d2.count(cur)){
return step+d2[cur];
}
d1[cur]=step+1;
q1.push(cur);
}
cur[p]=old;
}
}
}
else{
int sz=q2.size();
for(int i=0;i<sz;i++){
string cur=q2.front();
q2.pop();
int step=d2[cur];
for(int p=0;p<cur.size();p++){
char old=cur[p];
for(char c='a';c<='z';c++){
if(c==old) continue;
cur[p]=c;
if(!dict.count(cur)) continue;
if(d2.count(cur)) continue;
if(d1.count(cur)){
return step+d1[cur];
}
d2[cur]=step+1;
q2.push(cur);
}
cur[p]=old;
}
}
}
}
return 0;
}
int main(){
string b,e;
cin>>b>>e;
unordered_set<string> dict;
string w;
while(cin>>w) dict.insert(w);
int ans=bdbfs(b,e,dict);
cout<<ans;
return 0;
}
有帮助，赞一个