实现了一个双向广度优先搜索（BFS）算法，用于解决字符串转换问题。给定两个字符串 A 和 B，以及一系列转换规则a[i]和b[i]，每次可以将字符串中的子串 a[i] 替换为 b[i]，目标是找到将字符串A转换为字符串B所需的最少步数，且步数不超过10步。如果无法在10步内完成转换，则输出 NO ANSWER!。

extend 函数：该函数用于从队列q中取出当前层的所有状态，并根据转换规则进行扩展。da 存储从起始状态到当前状态的步数，db存储从目标状态到当前状态的步数。通过两层循环遍历所有规则和字符串的所有可能位置，找到可替换的子串并生成新的字符串r。如果新字符串r已经在db中出现，说明双向搜索相遇，返回总步数。如果新字符串r已经在da中出现，说明该状态已经扩展过，跳过。
bfs 函数：初始化两个队列q1和q2，分别存储从起始状态和目标状态开始扩展的状态。初始化两个哈希表qa和qb，分别记录从起始状态和目标状态到当前状态的步数。每次选择队列元素较少的一方进行扩展，以平衡搜索空间。
如果扩展过程中找到解且步数不超过10，返回总步数；如果步数达到10仍未找到解，返回 -1。

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

using namespace std;
const int N = 6;

string A,B;
string a[N],b[N];//规则

int n=0;

int extend(queue<string>& q, unordered_map<string,int>& da, unordered_map<string, int>& db,string a[], string b[])
{
    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.count(r)) continue;
                    da[r]=da[t]+1;
                    q.push(r);
                }
            }
        }
    }
    return 11;
}

int bfs()
{
    if (A == B) return 0;
    queue<string>q1,q2;//存放起点和终点的拓展点
    unordered_map<string,int>qa,qb;//步数

    q1.push(A),qa[A]=0;
    q2.push(B),qb[B]=0;
    int step = 0;
    while(q1.size()&&q2.size())
    {
        int t;
        if(q1.size()<q2.size()) t = extend(q1,qa,qb,a,b);
        else  t = extend(q2,qb,qa,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;
}