话说写这篇题解的初衷,是给自己看的……
如果写的有些纰漏,敬请谅解
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
const int N=6;
int n;
string A,B;
string a[N],b[N];
int extend(queue<string>&q,unordered_map<string, int>&da,unordered_map<string,int>&db,string a[N],string b[N]){
int d=da[q.front()];
while (q.size()&&da[q.front()]==d){ //保持遍历同一层
auto t = q.front();
q.pop();
for (int i=0;i<n;i++)
for (int j=0;j<t.size();j++)
if (t.substr(j,a[i].size())==a[i]){
//试着将原字符串按第i条变换规则变换
string r=t.substr(0,j)+b[i]+t.substr(j+a[i].size());
if (db.count(r)) //两端出现交集
return da[t]+db[r]+1;
if (da.count(r)) //该字符串已被遍历过
continue;
da[r]=da[t]+1;
q.push(r);
}
}
return 11; //当前层没出现交集,就返回任意比10大的数
}
int bfs()
{
if (A==B) return 0;
queue<string> qa,qb; //分别储存两头出发的队列
unordered_map<string,int> da,db; //分别储存字符串到开头和结尾的“距离”
qa.push(A), qb.push(B);
da[A] = db[B] = 0;
int step=0;
while (qa.size()&&qb.size()){ //两个队列均不为空,还有可能存在交集
int t;
if (qa.size()<qb.size()) //遍历较短的队列
t=extend(qa,da,db,a,b);
else
t=extend(qb,db,da,b,a);
if (t<=10) //当前层存在交集
return t;
if (++step==10) //超过10层,无法在10步以内将A变换为B
return -1;
}
return -1; //直到队列为空都不存在交集,无法将A变换为B
}
int main()
{
cin >> A >> B;
while (cin>>a[n]>>b[n]) n ++; //读入变换规则
int t=bfs();
if (t==-1)
puts("NO ANSWER!");
else
cout<<t<<endl;
return 0;
}