莫欺少年穷，修魔之旅在这开始—>算法提高课题解

保姆级注释，看不懂你炸我

双向广搜

思路：

1. da 和 db 表示距离各自起点的步数
2. 每次取元素较少的队列来扩展，以达到相对平衡
3. 每次扩展的都是这一层的元素，如果 qa 扩展的元素在 qb 中出现过，就 return 步数
4. 否则，放入队列，并更新距离起点的步数

#include<bits/stdc++.h>

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[],string b[])
{
    //取出这一层的距离起点的步数
    int d=da[q.front()];

    //如果队列空了或扩展的元素到达下一层了，就return
    while(q.size()&&d==da[q.front()])
    {
        //取出队头
        auto t=q.front();
        q.pop();

        //枚举所有起点
        for(int i=0;i<t.size();i++)

            //枚举所有规则
            for(int j=0;j<n;j++)
                if(t.substr(i,a[j].size())==a[j])
                {
                    //该元素新扩展出来的字符串
                    string state=t.substr(0,i)+b[j]+t.substr(i+a[j].size());

                    //之前出现过
                    if(da.count(state)) continue;

                    //在db数组里面出现过，直接return步数
                    if(db.count(state)) return da[t]+1+db[state];

                    //放入队列并更新步数
                    q.push(state);
                    da[state]=da[t]+1;
                }
    }

    return 11;
}

int bfs()
{
    //两个字符串相等，直接return
    if(A==B) return 0;

    //初始化qa和qb两个队列
    queue<string> qa,qb;
    qa.push(A),qb.push(B);

    //初始化da和db两个距离各自起点的步数
    unordered_map<string,int> da,db;
    da[A]=0,db[B]=0;

    //记录走的步数，超过10步直接return
    int step=0;

    //如果其中一个没了，就说明不连通，直接return -1；
    while(qa.size()&&qb.size())
    {
        //取元素较少的队列来扩展，达到相对平衡
        int t;
        if(qa.size()<=qb.size()) t=extend(qa,da,db,a,b);
        else t=extend(qb,db,da,b,a);

        //两个字符串相聚，且步数不超过10
        if(t<=10) return t;

        //步数超10，直接return
        if(++step==10) return -1;
    }

    return -1;
}

int main()
{
    cin>>A>>B;

    while(cin>>a[n]>>b[n]) n++;

    if(bfs()==-1) cout<<"NO ANSWER!"<<endl;
    else cout<<bfs()<<endl;

    return 0;
}