cin>>tt是什么意思?
by az__eg @ 2022-07-14 20:19:29
```cpp
#include<bits/stdc++.h>
using namespace std;
string a,b;//原字符串和目标字符串
int ans=11;
int cnt=0;
int dq = 0;
struct change{
string s1,s2;
}aa[105];//可以转换的字符串对应关系
string xs;
void dfs(int dep)
{
// cout<<xs<<endl;
if(dep>=dq)
{
return;
}
for(int i=0;i<cnt;i++)
{
if(ans!=11)
{
return;
}
if(xs.size()>=aa[i].s1.size())
{
for(int j=0;j<xs.size()-aa[i].s1.size()+1;j++)
{
if(ans!=11)
{
return;
}
bool flag=1;
for(int k=0;k<aa[i].s1.size();k++)
{
if(ans!=11)
{
return;
}
if(xs[j+k]!=aa[i].s1[k])
{
// int tt;
// cin>>tt;
flag=0;
break;
}
}
if(flag==1)
{
string past = xs;
xs = xs.substr(0,j)+aa[i].s2+xs.substr(j+aa[i].s1.size(),xs.size());
if(xs==b)
{
ans = min(ans,dep+1);
return;
}
dfs(dep+1);
xs = past;
}
}
}
}
}
//搜索写的很复杂,因为是自己写的查找子串,用find()函数的话只能返回第一个查到的位置,还要配erase(),思维上有点绕
int main(){
cin>>a>>b;
if(a==b)
{
printf("0\n");
return 0;
}
string xx,yy;
while(cin>>xx>>yy){
aa[cnt].s1=xx;
aa[cnt].s2=yy;
cnt++;
}
xs = a;
for(int i=1;i<=10;i++)
{
dq = i;
dfs(0);
if(ans!=11)
{
printf("%d",ans);
return 0;
}
}
if(ans==11){
cout<<"NO ANSWER!";
}else{
cout<<ans;
}
return 0;
}
```
by az__eg @ 2022-07-14 20:33:08
使用迭代加深算法,这个空间复杂度低
by az__eg @ 2022-07-14 20:33:45
@[HMR202001](/user/575093) 不要用bfs了,空间特别容易爆炸,用dfs,然后设置一个循环从1~n,每循环一次dfs一次,然后dfs(x)表示当前步数,如果x比i大,先不考虑,这样的话实际就是跟bfs一样,然后再加些剪枝,跑得飞快
by az__eg @ 2022-07-14 20:35:41
@[mmdxm](/user/229801) 啊,调试的时候写的,忘删掉了
by HMR202001 @ 2022-07-14 20:58:52
@[HMR202001](/user/575093) 不用谢
by az__eg @ 2022-07-14 21:00:03
@[mmdxm](/user/229801) 谢谢指点
by HMR202001 @ 2022-07-14 21:01:37
(什么也没发生…)
啊
关于我用错表情删楼导致顺序神奇这件事
by HMR202001 @ 2022-07-14 21:06:10