~~变量名好随意啊~~
by Belarus @ 2020-02-13 19:19:01
@[Belarus](/user/223392) 窝一般都是qwq,orz,sto,qaq,qwertyuiop之类的
by sc84bbs @ 2020-02-13 19:20:49
O2
by JRzyh @ 2020-02-28 10:16:11
map的清空是O(log n)的吧
by JRzyh @ 2020-02-28 10:35:01
@[自动RE机](/user/217743) 还剩1TLE
```cpp
#include<bits/stdc++.h>
using namespace std;
string a,b,w[10],m[10];
int n,ans=1e8;
bool ok;
map<string,bool>mp;
void dfs(int d)
{
if(mp[a]) return;
if(a==b)
{
ans=min(ans,d);
ok=1;
return;
}
mp[a]=1;
if(d>10) return;
for(int i=0;i<n;i++)
{
int c=a.find(w[i]);
while(c<a.length()&&c>=0)
{
string temp=a;
a.replace(c,w[i].length(),m[i]);
dfs(d+1);
a=temp;
c=a.find(w[i],c+1);
}
}
}
int main()
{
cin>>a>>b;
while(cin>>w[n]>>m[n])n++;
mp.clear();
dfs(0);
if(ok&&ans<=10&&ans!=0)
{
cout<<ans;
return 0;
}
else
{
printf("NO ANSWER!");
return 0;
}
return 0;
}
```
by JRzyh @ 2020-02-28 11:05:44
换一下方法吧,我觉得单纯靠找到答案就不搜了的这种剪枝,很难不超时。最后一个点深度已经很接近10了,并且那份输入数据很容易把dfs卡死在深层。
by WanderOvO @ 2020-04-04 10:26:51