@[liuzimingc](/user/421781)
自己发现了一个错误,但还是输出 $1$,疯了,把注释的去掉又直接 $\texttt{NO ANSWER!}$。
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
#define maxn 10
#define ll long long
string A,B,x[maxn],y[maxn];
struct node{
string s;
int foot;
};
queue<node> Q;
map<string,int> vis;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>A>>B;
int n=0,ans=0;
while (cin>>x[n]>>y[n]) n++;
Q.push((node){A,0});
node u;
while (!Q.empty()){
u=Q.front();
string us=u.s;
int ufoot=u.foot;
Q.pop();
if (us==B){
ans=ufoot;
break;
}
for (int i=0;i<n;i++)
if (int(us.find(x[i]))!=-1 && vis[us]==0){
//下面的作用就是把us的x[i]的部分替换成y[i];
int k=int(us.find(x[i]));
us.erase(k,k+x[i].length());
us.insert(k,y[i]);
Q.push((node){us,ufoot+1});
//vis[us]=1;
}
}
if (ans>10 || ans==0) cout<<"NO ANSWER!"<<endl;
else cout<<ans<<endl;
return 0;
}
```
by liuzimingc @ 2021-01-26 21:09:11
us在每次循环之后要改回队头,不然,如果一个队头有多种替换方案,你的us就会替换多次。
```cpp
for (int i=0;i<n;i++)
string nowstring = us;
if (int(us.find(x[i]))!=-1 && vis[us]==0){
//下面的作用就是把us的x[i]的部分替换成y[i];
int k=int(us.find(x[i]));
nowstring.erase(k,k+x[i].length());
nowstring.insert(k,y[i]);
Q.push((node){us,ufoot+1});
//vis[us]=1;
}
```
格式混乱,瞎改了几笔。大概没人能看懂。
by imfkwk @ 2021-01-26 21:32:16
@[I_love_your_mother](/user/389540) 把
`Q.push((node){us,ufoot+1});`
改成
`Q.push((node){nowstring,ufoot+1});`
大概就可以了(另外,你bfs打标了吗?)
by imfkwk @ 2021-01-26 21:34:10
@[I_love_your_mother](/user/389540)
~~打标是什么意思?~~
by liuzimingc @ 2021-02-03 08:06:55
@[liuzimingc](/user/421781) 就是打标记啊,免得回搜。如果当前状态已经有过了,那肯定不要再搜过去一次啊
by imfkwk @ 2021-02-03 08:55:06
@[I_love_your_mother](/user/389540)
打了……
by liuzimingc @ 2021-02-03 19:17:19
@[liuzimingc](/user/421781) 那我就不知道了,我是个屑
by imfkwk @ 2021-02-03 19:54:56
@[I_love_your_mother](/user/389540)
已经AC了,哈!
by liuzimingc @ 2021-02-03 19:57:37
@[I_love_your_mother](/user/389540)
[look here.](https://www.luogu.com.cn/record/list?user=421781)
by liuzimingc @ 2021-02-03 20:00:45