备战蓝桥杯—搜索（优化1）

本文介绍: 我们可以先从头变换5次，再从尾变换5次，然后对两组dis进行拼接。这样就把6^10降成了6^5*2。结果只过了87.5的数据（qaq)

显然，我们可以用BFS解决，具体实现与八数码类似：

下面是代码：

#include<bits/stdc++.h>
using namespace std;
#define N 3000000
string a,b;
int hh,dis[N],cnt;
struct node{
    string u,v;
}bian[7];
map<string,int> mp;
string huan[N];
queue<int> q;
int bfs(string a,string b){
    mp[a]=1;
    huan[++cnt]=a;
    dis[cnt]=0;
    q.push(cnt);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        if(dis[tmp]==10) return 0;
        string now=huan[tmp];
        for(int i=1;i<=hh;i++){
            for(int j=0;j<now.length();){
                 string nxt=now;
                int pos=now.find(bian[i].u,j);
                if(pos<0&&pos>=now.length()) break;
                j=pos+1;
                nxt.erase(pos,bian[i].u.length());
                nxt.insert(pos,bian[i].v);
                if(mp.find(nxt)!=mp.end()) continue;
                if(nxt.length()>20) continue;
                dis[++cnt]=dis[tmp]+1;
                mp[nxt]=cnt;
                huan[cnt]=nxt;
                q.push(cnt);
                if(nxt==b) return dis[cnt];
            }
        }
    }
    return 0;
}
int main(){
    cin>>a>>b;
    while(cin>>bian[++hh].u>>bian[hh].v) ;
    int u=bfs(a,b);
    if(!u) cout<<"NO ANSWER!";
    else cout<<u;
}

结果只过了87.5的数据（qaq)

实际上，这题虽然说只有6种变换法则，但是如果给的字符串恶心一点（比如适用同一法则的pos位置有很多，那么它的复杂度铁定远大于6^10,于是我们可以优化一下：

#include<bits/stdc++.h>
using namespace std;
#define N 1000000
string a,b;
int hh,disA[N],cnt,disB[N];
struct node{
    string u,v;
}bian[7];
map<string,int> mp;
string huan[N];
queue<int> q;
int bfs(string a,string b,int y,int dis[]){
    while(!q.empty()) q.pop();
    mp[a]=++cnt;
    huan[cnt]=a;
    dis[cnt]=0;
    q.push(cnt);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        if(dis[tmp]==5) return 0;
        string now=huan[tmp];
        for(int i=1;i<=hh;i++){
            for(int j=0;j<now.length();){
                 string nxt=now;
                if(y==1){
                int pos=now.find(bian[i].u,j);
                if(pos<0&&pos>=now.length()) break;
                j=pos+1;
                nxt.erase(pos,bian[i].u.length());
                nxt.insert(pos,bian[i].v);}
                if(y==0){
                int pos=now.find(bian[i].v,j);
                if(pos<0&&pos>=now.length()) break;
                j=pos+1;
                nxt.erase(pos,bian[i].v.length());
                nxt.insert(pos,bian[i].u);}   
                if(nxt.length()>20) continue;
                if(mp.find(nxt)!=mp.end()&&dis[mp[nxt]]!=-1) continue;
                if(mp.find(nxt)==mp.end()){
                dis[++cnt]=dis[tmp]+1;
                mp[nxt]=cnt;
                huan[cnt]=nxt;
                q.push(cnt);}
                else{
                    dis[mp[nxt]]=dis[tmp]+1;
                    q.push(mp[nxt]);
                }
            }
        }
    }
    return 0;
}
int main(){
    cin>>a>>b;
    while(cin>>bian[++hh].u>>bian[hh].v) ;
    memset(disA,-1,sizeof(disA));
    memset(disB,-1,sizeof(disB));
    bfs(a,b,1,disA);
    bfs(b,a,0,disB);
    int min1=11;
    for(int i=1;i<=cnt;i++){
        if(disA[i]!=-1&&disB[i]!=-1)
        min1=min(min1,disA[i]+disB[i]);
    }
    if(min1>10) cout<<"NO ANSWER!";
    else cout<<min1;
}

显示所有内容

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。