打错了是80分
by Eric12 @ 2022-08-29 21:51:20
问题已解决，没用vis数组标记会导致重复入队，这回造成MLE，这是我的AC代码：
```cpp
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
string a,b;
int i,index;
struct rule{
string re;
string pre;
}r[1001];
struct node{
string str;
int step;
};
void fakebfs()
{
queue<node> q;
map<string,bool> vis;
q.push({a,0});
// cout<<0<<' '<<a<<endl;
while(!q.empty())
{
node x=q.front();
if(x.str==b)
{
cout<<x.step<<endl;
return;
}
if(x.step>=10)
{
cout<<"NO ANSWER!"<<endl;
return;
}
for(i=1;i<index;i++)
{
int zancun=0,zc=x.str.find(r[i].re,zancun);
while(zc!=string::npos)
{
node next;
next.str=x.str;
next.str.replace(zc,r[i].re.size(),r[i].pre);
next.step=x.step+1;
if(!vis[next.str])
{
vis[next.str]=true;
// cout<<r[i].re<<' '<<zc<<' '<<zc+r[i].re.size()<<' '<<next.step<<' '<<next.str<<endl;
q.push(next);
}
zancun=zc+1;
zc=x.str.find(r[i].re,zancun);
}
}
q.pop();
}
cout<<"NO ANSWER!"<<endl;
}
int main()
{
cin>>a>>b;
for(i=1;cin>>r[i].re>>r[i].pre;i++)
;
index=i;
fakebfs();
return 0;
}
```
by Eric12 @ 2022-08-29 22:50:32