acwing190. 字串变换

题目

已知有两个字串 A, B 及一组字串变换的规则（至多 6 个规则）:

A1→B1
A2→B2
…

规则的含义为：在 A 中的子串 A1 可以变换为 B1、A2 可以变换为 B2…。

例如：A＝abcd B＝xyz

变换规则为：

abc → xu ud → y y → yz

则此时，A 可以经过一系列的变换变为 B，其变换的过程为：

abcd → xud → xy → xyz

共进行了三次变换，使得 A 变换为 B。

题解

题目中每次搜索有6种变换，最多有10次变换，如果只从起点开始bfs那么需要10的6次方，效率太慢，可以从起点和终点一起搜索，这样只需要2*10^5，效率会提升不少。

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=6;
int n;
string A,B;
string a[N],b[N];
int extend(queue<string>&q,unordered_map<string,int>&da,unordered_map<string,int>&db,string a[N],string b[N]){
    int d=da[q.front()];
    while(q.size()&&da[q.front()]==d){
        auto t=q.front();
        q.pop();
        for(int i=0;i<n;i++){
            for(int j=0;j<t.size();j++){
                if(t.substr(j,a[i].size())==a[i]){
                    string r=t.substr(0,j)+b[i]+t.substr(j+a[i].size());
                    if(db.count(r))return da[t]+db[r]+1;
                    if(da[r])continue;
                    da[r]=da[t]+1;
                    q.push(r);
                }
            }
        }
    }
    return 11;
}
int bfs(){
    if(A==B)return 0;
    queue<string>qa,qb;
    unordered_map<string,int>da,db;
    qa.push(A),qb.push(B);
    da[A]=db[B]=0;
    int step=0;
    while(qa.size()&&qb.size()){
        int t=0;
        if(qa.size()<qb.size())t=extend(qa,da,db,a,b);
        else t=extend(qb,db,da,b,a);
        if(t<=10)return t;
        if(++step==10)return -1;
    }
    return -1;
}
int main(){
    cin>>A>>B;
    while(cin>>a[n]>>b[n])n++;
    int t=bfs();
    if(t==-1)puts("NO ANSWER!");
    else cout<<t<<endl;
    
    return 0;
}