字串变换--距离***搜索结束还有6题

闲谈:emm,明天开始就要自闭了,今天的题水的一批,自己还水了那么久的群,以及水了一个考试,还看cyq直播,真的shabi...
双向bfs往往比单向bfs更优,至于为什么?自己画个图就懂了?
下面讲讲这个题怎么做?
双向bfs两个点,起点和终点.然后进行枚举每个变换..最后有交接就是答案了.
代码:(建议双向广搜就拿这个当模板吧)

#include <bits/stdc++.h>
using namespace std;
const int N=6;
string A,B;
int n=0;
string a[N],b[N];

int extend(queue<string>&q,unordered_map<string,int>&disa,unordered_map<string,int>&disb,string a[],string b[])
{
    auto t=q.front();q.pop();
    for(int i=0;i<(int)t.size();i++)//枚举每个变换的起点.
    {
        for(int j=0;j<n;j++)//枚举可能的变换.
        {
            if(t.substr(i,a[j].size())!=a[j]) continue;
            string new_t=t.substr(0,i)+b[j]+t.substr(i+a[j].size());
            if(disa.count(new_t)) continue;
            if(disb.count(new_t)) return disa[t]+disb[new_t]+1;
            disa[new_t]=disa[t]+1;
            q.push(new_t);
        }
    }
    return -1;
}

int bfs()//对A和B进行bfs.
{
    unordered_map<string,int>disa,disb;//从起点搜的距离和从终点搜的距离.
    queue<string>qa,qb;
    qa.push(A);disa[A]=0;
    qb.push(B);disb[B]=0;
    while(qa.size()&&qb.size())//假如两个中一旦有一个不能扩展了,那么就可以直接退出了.
    {
        int t;
        if(disa[qa.front()]+disb[qb.front()]>10) return 11;
        if(qa.size()<=qb.size()) //搜起点.
        {
            t=extend(qa,disa,disb,a,b);
        }
        else//搜终点.
        {
            t=extend(qb,disb,disa,b,a);
        }
        if(t!=-1) return t;
    }
    return 11;
}

int main()
{
    cin>>A>>B;
    while(cin>>a[n]>>b[n]) n++;//n个字符串
    //a->b.
    if(bfs()>10)    puts("NO ANSWER!");
    else            cout<<bfs()<<endl; 
    return 0;
}