这是80分的代码:
#include<bits/stdc++.h>
using namespace std;
string a, b, ai, bi;
int idx, pos;
typedef pair<string, int> PSI;
typedef pair<string, string> PSS;
PSS cha[100];
queue<PSI>q;
int bfs(string st)
{
q.push({ st,0 });
while (q.size())
{
auto t = q.front().first; // 某一个状态的字符串
int dep = q.front().second; // 某一个状态的层数
if (dep > 10) return -1;
q.pop();
for (int i = 1; i <= idx; i++)
{
string tem = t;
int pos = -1;
string ai = cha[i].first;
string bi = cha[i].second;
while ((pos = tem.find(ai.c_str())) != -1)
{
tem.replace(pos, ai.size(), bi.c_str());
if (tem == b) return dep + 1;
q.push({ tem,dep + 1 });
}
}
}
return -1;
}
int main()
{
cin >> a >> b;
while (cin >> ai >> bi)
cha[++idx] = { ai,bi }; //绑定
if (a == b)
{
printf("0");
return 0;
}
int ans = bfs(a);
if (ans == -1) printf("NO ANSWER!");
else cout << ans;
return 0;
}