题目链接 https://www.luogu.org/problemnew/show/P1032
本题是一道bfs问题，从a串开始，每一步完成替换一对字符串（但是一个一步替换可以将这对字符串替换好几次，比如a串是 ABCABCABCABC 一对替换是BC替换成ED，那么一步替换是将 ABCABCABCABC 替换成 AEDAEDAEDAED ）如果十步以内转换成b就输出
本题还让蒟蒻学习了一下map的用法 真的十分好用 c++的stl真是A题利器
具体放代码吧：
#include<bits/stdc++.h> using namespace std; string a,b;
string sa[],sb[];
map<string,int>maps; //用来判重，达到剪枝的效果
queue<string>q; //用来存转换出的字符串
queue<int>nq; //存当前的步数
int n,k=-; void bfs()
{
int i;
while(!q.empty())
{
if(nq.front()>) //超过十步，跳出循环
break;
if(q.front()==b)
{
k=nq.front(); //到了b就更新k 跳出
break;
}
if(maps[q.front()]==) //如果当前的字符串搜索过，就pop掉 别忘了continue！
{
q.pop();
nq.pop();
continue;
}
maps[q.front()]=; //没有的话就标记上 起到剪枝的效果 for(i=;i<n;i++)
{
string s=q.front(),ss;
while()
{
int m=s.find(sa[i]); //寻找第一次出现sa[i]的位置
if(m==-) //找不到 说明能和sa[i]换的都换了 跳出while循环
break;
ss=q.front();
ss.replace(m,sa[i].size(),sb[i]);
q.push(ss);
nq.push(nq.front()+);
s[m]='#'; //将匹配的地方替换成一个不相关的字符，这样就可以找到下一个匹配的地方
}
}
q.pop();
nq.pop();
}
if(k==-)
cout<<"NO ANSWER!";
else
cout<<k;
} int main()
{
cin>>a>>b;
while(cin>>sa[n]>>sb[n]) //因为不知道会输入几个字符串，需要用while输入
n++;
q.push(a);
nq.push();
bfs();
}