我为什么错了第五点,手动演算也是没有问题的,为什么会错呢?求解释。
#include <bits/stdc++.h>
using namespace std;
string sts, eds, x[10], y[10];
int id;
bool flag = 0;
struct que{
string s;
int step;
};
map <string, string> tran;
map <string, bool> vis;
void bfs(string sts){
queue <que> q;
q.push({sts, 0});
vis[sts] = 1;
while(!q.empty()){
string xx = q.front().s;
int step = q.front().step; q.pop();
if(xx == eds){
cout << step << "\n";
flag = 1;
return ;
}
if(step == 10)
continue;
for(int i = 1; i <= id; i++){
int j = 0;
while(xx.find(x[i], j) != string::npos){
int p = xx.find(x[i], j);
string nx = xx.substr(0, p) + y[i] + xx.substr(p + x[i].size());
if(vis[nx])
break;
vis[nx] = 1;
q.push({nx, step + 1});
j = p + x[i].size();
}
}
}
}
int main(){
cin >> sts >> eds;
while(cin >> x[++ id] >> y[id]){
tran[x[id]] = y[id];
}
bfs(sts);
if(!flag)
cout << "NO ANSWER!" << "\n";
return 0;
}