C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>//比map稍微快一点
#include<queue>

using namespace std;

const int N=6;

int n;
string a[N], b[N];//每次操作的对象都是字符串

int extend(queue<string>& q, unordered_map<string, int>& da, unordered_map<string, int>& db, string a[], string b[])
{
    //之前y总在提高课的视频中，每次只扩展一条边，显然不对
    //他后来打卡代码中改了，每次扩展一层，这样就保证正确了
    //这一趟需要把队列中的可以扩展的都搜完
    for(int k=0, sk=q.size(); k<sk; k++)
    {
        //每一次取出一个字符串状态，直到取完
        string t=q.front();
        q.pop();

        //看一下哪些子串可以进行扩展操作
        for(int i=0, kt=t.size(); i<kt; 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());//默认到最后了
                    //看看这个新的状态da中有没有，有的话，就不用入队了，直接continue
                    if(da.count(state)) continue;
                    if(db.count(state)) return da[t]+1+db[state];//db中有新状态直接返回
                    da[state]=da[t]+1;
                    q.push(state);

                }
            }

    }

    return 11;//扩展不到的话，返回正无穷
}

int bfs(string A, string B)
{
    queue<string> qa, qb;//两个队列，一个从头开始，一个倒着开始
    unordered_map<string, int> da, db;//每一个状态走了多少步要记录一下
    qa.push(A), da[A]=0;
    qb.push(B), db[B]=0;

    while(qa.size() && qb.size())//两个均不空才搜
    {
        int t;
        //跳一下扩展选择比较少的队列进行搜 
                                    //扩展qa，a-》b
        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;

    }   

    return 11;
}

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

    //不知道有多少种扩展方式，所以读入数据的时候记录一下
    while(cin>>a[n]>>b[n]) n++;

    int step=bfs(A, B);
    if(step>10) puts("NO ANSWER!");
    else printf("%d\n", step);

    return 0;
}