string操作
只需要知道string的replace,和其他的,就可以很方便的A了它
用str替换指定字符串从起始位置pos开始长度为len的字符 .
再加一些简单的剪枝
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
string s,e,a[20],b[20];
int lena[20],lenb[20],cnt=1,mx=0,mn=0;
map<string,int>m;
inline void dfs(string x,int k) {
if(k>=10)return;
int v=x.size(),p=e.size();
if((v+mx*(10-k)<p)||(v+mn*(10-k)>p))return;
k++;
for(int i=1; i<=cnt; i++) {
int pos=x.find(a[i],0);
while(pos!=string::npos) {
string tmp=x;
tmp.replace(pos,lena[i],b[i]);
if((!m[tmp]&&tmp!=s)||(m[tmp]>m[x]+1))
m[tmp]=m[x]+1,dfs(tmp,k);
pos=x.find(a[i],pos+1);
}
}
}
int main() {
cin>>s>>e;
while(cin>>a[cnt]>>b[cnt]) {
lena[cnt]=a[cnt].size();
lenb[cnt]=b[cnt].size();
mn=min(mn,lenb[cnt]-lena[cnt]);
mx=max(mx,lenb[cnt]-lena[cnt]);
cnt++;
if(cnt>6)break;
}
cnt--;
dfs(s,0);
if(m[e])cout<<m[e];
else cout<<"NO ANSWER!";
return 0;
}
wa 的代码
少了一个特判
c++ 的语法好强大
tql!!!库函数大佬