#include<bits/stdc++.h>
using namespace std;
struct node{
int steps;
string sent;
};
queue<node> change;
map<string,int> vis;
string fir[10],sec[10],a,b;
int n;
string turn(string tar,int pos,int cho){
int i;
string fin="";
if(fir[cho].length()+pos>tar.length())return fin;
for(i=pos;i<pos+fir[cho].length();i++){
if(tar[i+pos]!=fir[cho][i])return fin;
}
fin+=tar.substr(0,pos);
fin+=sec[cho];
fin+=tar.substr(pos+fir[cho].length());
return fin;
}
void bfs(){
node tmp,cur;
string str;
int i,j;
tmp.sent=a;
tmp.steps=0;
change.push(tmp);
while(!change.empty()){
cur=change.front();
change.pop();
if(cur.sent==b){
break;
}
if(vis[cur.sent]==1){
continue;
}
vis[cur.sent]=1;
for(i=0;i<cur.sent.length();i++){
for(j=0;j<n;j++){
str=turn(cur.sent,i,j);
if(str!=""){
tmp.sent=str;
tmp.steps=cur.steps+1;
change.push(tmp);
}
}
}
}
if(cur.steps>10||cur.sent!=b)cout<<"NO ANSWER!";
else cout<<cur.steps;
}
int main(){
int i;
//n=6;
cin>>a>>b;
while(cin>>fir[n]>>sec[n])n++;
//for(i=0;i<n;i++)cin>>fir[i]>>sec[i];
//while(fir[n][0]=='\0')n--;
bfs();
return 0;
}
以上是输入方案一,测评结果为第4点WA,其余点RE。 如果将所有注释号去掉,并注释倒数第六行,变成了输入方案二,即:
int main(){
int i;
n=6;
cin>>a>>b;
//while(cin>>fir[n]>>sec[n])n++;
for(i=0;i<n;i++)cin>>fir[i]>>sec[i];
while(fir[n][0]=='\0')n--;
bfs();
return 0;
}
结果是第4点RE,第3点TLE,其余点WA。 这道题的输入困扰我很久了,请问哪位大佬能帮忙解决一下!