现在60
```cpp
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
string r1[15],r2[15];
int len1[15];
int k,fi;
int len;
map<string,int> flag,mark;
queue<string> q[5];
int doublebfs(){
flag[s1]=0;
flag[s2]=0;
mark[s1]=1;
mark[s2]=2;
q[1].push(s1);
q[2].push(s2);
string x,y;
int fx;
while(!q[1].empty()&&!q[2].empty()){
if(q[1].size()>q[2].size()) fx=2;
else fx=1;
x=q[fx].front();
q[fx].pop();
if(flag[x]>10) continue;
for(int i=1;i<=k;i++){
int ft=0;
while(ft<=len){
int fi=x.find(r1[i],ft);
if(fi!=-1){
y=x;
y.replace(fi,len1[i],r2[i]);
//cout<<y<<" "<<i<<" "<<fx<<endl;
if(mark[x]&&mark[y]&&mark[x]!=mark[y]){
int t=flag[x]+flag[y]+1;
if(t>10) continue;
return t;
}
if(!mark[y]){
mark[y]=mark[x];
flag[y]=flag[x]+1;
q[fx].push(y);
}
}else break;
ft=fi+1;
}
}
}
return -1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>s1>>s2;
for(int i=1;i<=6;i++){
cin>>r1[i]>>r2[i];
len1[i]=r1[i].size();
}
for(int i=1;i<=6;i++){
if(!len1[i]){
break;
}
k=i;
}
len=s1.size();
int dn=doublebfs();
if(dn==-1) cout<<"NO ANSWER!";
else cout<<dn;
return 0;
}
```
by Addicted_Game @ 2023-10-26 20:45:27
```cpp
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
string r1[15][5];
int len1[15][5];
int k,fi;
int len;
map<string,int> flag,mark;
queue<string> q[5];
int doublebfs(){
flag[s1]=0;
flag[s2]=0;
mark[s1]=1;
mark[s2]=2;
q[1].push(s1);
q[2].push(s2);
string x,y;
int fx,ffx;
while(!q[1].empty()&&!q[2].empty()){
if(q[1].size()>q[2].size()) fx=2,ffx=1;
else fx=1,ffx=2;
x=q[fx].front();
q[fx].pop();
//cout<<x<<" qd "<<mark[x]<<endl;
if(flag[x]>10) return -1;
for(int i=1;i<=k;i++){
int fi=x.find(r1[i][fx],0);
//cout<<r1[i]<<" cx\n";
while(fi<=len){
fi=x.find(r1[i][fx],fi);
if(fi!=-1){
y=x;
y.replace(fi,len1[i][fx],r1[i][ffx]);
//cout<<y<<" "<<i<<" "<<fx<<endl;
if(!mark[y]){
//cout<<y<<" rd "<<fx<<endl;
mark[y]=mark[x];
flag[y]=flag[x]+1;
q[fx].push(y);
}
if(mark[x]&&mark[y]&&mark[x]!=mark[y]){
int t=flag[x]+flag[y]+1;
if(t>10) return -1;
return t;
}
}else break;
fi++;
}
}
}//问题:末尾无法搜索延伸,所以被迫停止
return -1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>s1>>s2;
for(int i=1;i<=6;i++){
cin>>r1[i][1]>>r1[i][2];
len1[i][1]=r1[i][1].size();
len1[i][2]=r1[i][2].size();
}
for(int i=1;i<=6;i++){
if(!len1[i][1]){
break;
}
k=i;
}
len=s1.size();
int dn=doublebfs();
if(dn==-1) cout<<"NO ANSWER!";
else cout<<dn;
return 0;
}
/*
abcdefgh 12345678
abcd efgh
efgh 1234
efgh 5678
3
*/
```
过了
问题:搜索时,要注意两个方向搜索的起点与终点不同(fx ffx)
by Addicted_Game @ 2023-10-28 00:01:29