题目描述

每次选择队列长度较小的一个方向扩展

双向广搜

#include <iostream>
#include <cstring>
#include <unordered_map>
#include <queue>

using namespace std;

string a[10],b[10];
int n=0;

int expand(queue<string> &q1,unordered_map<string,int> &d1,unordered_map<string,int> &d2,string a[],string b[])
{
    auto t=q1.front();
    q1.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(d2.count(state)) return d1[t]+1+d2[state];
                if(d1.count(state)) continue;
                d1[state]=d1[t]+1;
                q1.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;
    int t;
    while(qa.size()&&qb.size())
    {
        if(qa.size()>qb.size()) t=expand(qb,db,da,b,a);
        else t=expand(qa,da,db,a,b);
        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)
    cout<<step;
    else
    cout<<"NO ANSWER!";
    return 0;
}