最后一个点错了，我用的是iddfs算法+减枝
by LonginusMonkey @ 2023-07-13 16:08:49
同问，救助
```cpp
#include<bits/stdc++.h>
using namespace std;
int sum=1234,c=1;
string sr,ch;
string a[10],b[10];
void dfs(int path,string st){ //操作了几次,当前的字符串
if(path>10||path>sum)
return;
if(st==ch){
sum=min(path,sum);
return;
}
for(int i=1;i<c;i++){
if(st.find(a[i])!=string::npos){
string s1=st; //保存
int wz=st.find(a[i]),len=a[i].size();
string s2=st.replace(wz,len,b[i]);
dfs(path+1,s2);
st=s1; //回溯,很重要！！！
}
}
return;
}
int main(){
cin>>sr>>ch;
while(cin>>a[c]>>b[c]){
c++;
}
dfs(0,sr);
if(sum!=1234)
cout<<sum;
else
cout<<"NO ANSWER!";
return 0;
}
```
Orz
by guoshi @ 2023-07-19 19:11:55
@[Half_Monkey](/user/326254) @[guoshi](/user/945842) 我也是这么写的，但翻评论区发现是find的问题
by chen_z @ 2023-07-29 13:32:02
截取某大佬评论:显然一个字符串能在任意位置被交换成其他的字符串，但是只考虑了它第一次出现时的交换
by chen_z @ 2023-07-29 13:34:37
谢谢
by guoshi @ 2023-07-29 21:13:59
```cpp
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
int ans=114514;
int k,n;
string s,t,a,b,o[7];
map<string,string> tr;
map<string,bool> vis;
void dfs(string x,int depth){
if(depth>k||ans!=114514)return;
if(x==t){
ans=depth;
return;
}
for(int i=1;i<=n;i++){
int h=-1;
while(1919810){
h=x.find(o[i],h+1);
if(h==-1)break;
string y=x;
y.replace(h,o[i].length(),tr[o[i]]);
if(!vis[y]){
vis[y]=1;
dfs(y,depth+1);
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>s>>t;
while(cin>>a>>b){
++n;
tr[a]=b;
o[n]=a;
}
for(k=1;k<=10;k++)if(ans==114514){
vis.clear();
dfs(s,0);
}
if(ans==114514)cout<<"NO ANSWER!";
else cout<<ans;
return 0;
}
```
80分，WA#1
输出NO ANSWER,期望3
by 262620zzj @ 2023-08-16 15:11:11