```cpp
//同样这个应该60分的bfs也是全wa
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
using namespace std;
string a,b;
string ai[10],bi[10];
int ti=-1;
struct node
{
string ta;
int step;
}list[999];
void bfs()
{
int head=0,tail=1;
list[1].step=0;
list[1].ta=a;
while(head<tail)
{
head++;
if(list[head].step>10)
{
cout<<"NO ANSWER!";
exit(0);
}
else
{
for(int i=0;i<ti;i++)
{
node x=list[head];
unsigned int t=(x.ta).find(ai[i]);
if(t!=string::npos)
{
tail++;
(x.ta).replace((x.ta).find(ai[i]),ai[i].length(),bi[i]);
list[tail].ta=x.ta;
list[tail].step=list[head].step+1;
if(x.ta==b)
{
if(list[tail].step<=10)
cout<<list[tail].step;
else
cout<<"NO ANSWER!";
exit(0);
}
}
}
}
}
}
int main()
{
freopen("zifu.in.txt","r",stdin);
cin>>a>>b;
do
{
ti++;
cin>>ai[ti]>>bi[ti];
}while(!ai[ti].empty()&&!bi[ti].empty());
if(a!=b)
bfs();
else
cout<<0;
return 0;
}
```
by 泡末 @ 2017-09-23 19:07:37
……傻了，忘去掉freopen了……
by 泡末 @ 2017-09-23 19:18:54
去掉后第一个dfs全是wa…………多灾多难啊…………
by 泡末 @ 2017-09-23 19:50:14
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
string a,b;
string ai[999];
string bi[999];
int ti=0;
struct node
{
string data;
int step;
};
queue<node> q1;
queue<node> q2;
map<string,int> p1;
map<string,int> p2;
void expand1()
{
node t1=q1.front();
q1.pop();
for(int i=0;i<ti;i++)
{
unsigned int t=(t1.data).find(ai[i]);
if(t!=string::npos)
{
node tt=t1;
(tt.data).replace((tt.data).find(ai[i]),ai[i].length(),bi[i]);
tt.step=(t1.step)+1;//不可写成tt2.step++!!!!!!;
if(tt.step>10)
{
cout<<"NO ANSWER!";
exit(0);
}
if(p1.count(tt.data)==0)
{
p1.insert(pair<string,int>(tt.data,tt.step));
q1.push(tt);
map<string,int>::iterator it;
it=p2.find(tt.data);
if(it!=p2.end())
{
cout<<tt.step+it->second;
exit(0);
}
}
}
}
return;
}
void expand2()
{
node t2=q2.front();
q2.pop();
for(int i=0;i<ti;i++)
{
unsigned int t=(t2.data).find(bi[i]);
if(t!=string::npos)
{
node tt2=t2;
(tt2.data).replace((tt2.data).find(bi[i]),bi[i].length(),ai[i]);
tt2.step=(t2.step)+1;//不可写成tt2.step++!!!!!!!!;
if(tt2.step>10)
{
cout<<"NO ANSWER!";
exit(0);
}
if(p2.count(tt2.data)==0)
{
p2.insert(pair<string,int>(tt2.data,tt2.step));
q2.push(tt2);
map<string,int>::iterator it2;
it2=p1.find(tt2.data);
if(it2!=p1.end())
{
cout<<tt2.step+it2->second;
exit(0);
}
}
}
}
return;
}
void bfs()
{
node xa,xb;
xa.data=a;
xa.step=0;
xb.data=b;
xb.step=0;
q1.push(xa);
q2.push(xb);
p1.insert(pair<string,int>(xa.data,xa.step));
p2.insert(pair<string,int>(xb.data,xb.step));
int t=0;
while(!q1.empty()&&!q2.empty())
{
if(q1.size()<q2.size())
{
expand1();
}
else
{
expand2();
}
}
while(!q1.empty())
{
expand1();
}
while(!q2.empty())
{
expand2();
}
return;
}
int main()
{
freopen("zifu.in.txt","r",stdin);
cin>>a>>b;
//do
//{
// ti++;
// cin>>ai[ti]>>bi[ti];
//}while(!ai[ti].empty()&&!bi[ti].empty());
while(cin>>ai[ti]&&cin>>bi[ti])
ti++;
if(a!=b)
{
bfs();
}
else
cout<<0;
return 0;
}继续re
```
by 泡末 @ 2017-09-25 20:09:46
看大佬自言自语（手动滑稽）
by 皮某 @ 2017-09-26 23:02:58
##楼上+1
by 礼部尚书 @ 2017-09-27 17:12:18
时隔这么久，我找到bug了，是关于整形格式问题的，但是现在模板bfs只能到了80分，用严谨的逐层扩展dbfs没能判断步数（题解里的全是不严谨的交替扩展），所以现在dbfs的做法只有60分，当然手写不用模板我早过了…………
by 泡末 @ 2017-10-05 19:46:42
但这道题对于优化搜索很值得这样做
by 泡末 @ 2017-10-05 19:47:50
现在把空情况直接判0，dbfs走到了80分了……
by 泡末 @ 2017-10-05 20:10:53
Orz
by _小妖 @ 2018-02-03 19:28:05