题解 P1032 【字串变换】

风随逐影 · 2019-09-12 12:14:03 · 题解

迭代加深+剪枝

如果不加剪枝的话只有80分

看到变化次数不超过十想到迭代加深，但如果不加“在同一步数搜到相同的字符串就不能再搜”的剪枝是不能过的。

所以选择用map标记重复的，但迭代加深的话map需要清0，不能用memset，所以我选择每次新建一个map来交换

速度很快，最慢的点用了40ms

//剪枝：如果搜到相同的就不在搜了 
#include<bits/stdc++.h>
using namespace std;

#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define mp make_pair

typedef pair<string,short>pai;
const int inf=0x3f3f3f3f,N=10010;

int dep=0,n=1;
string A,B;
string a[N],b[N];
map<pai,bool>vis;

bool dfs(int now){
    if(now>dep) return 0;
    if(A==B) return 1;
    if(vis.count(mp(A,now))) return 0;
    vis[mp(A,now)]=1;
    string tmp=A;
    string x;
    go(i,1,n){
        unsigned int pos,np;
        if((pos=A.find(a[i]))==string::npos) continue;
        for(;pos<A.size();pos=np){
            x=A.substr(0,pos);
            x+=b[i];
            x+=A.substr(pos+a[i].size());
            A=x;
            if(dfs(now+1)) return 1;
            A=tmp;
            np=A.find(a[i],pos+a[i].size());
        }
    }
    return 0;
}

int main(){
    //freopen("input.txt","r",stdin);
    cin>>A>>B;
    while(cin>>a[n]>>b[n]) ++n;
    --n;
    while(!dfs(0)&&dep<=10){
        map<pai,bool>_new;
        swap(_new,vis);
        ++dep;
    }
    if(dep<=10) cout<<dep;
    else puts("NO ANSWER!");
    return 0;
}