双向广搜

思路

双向广搜通过从两端分别向中间搜索来降低时间复杂度，当两边搜到同一个字符串时意味着顺利会师，搜索结束。
如果任意一边在搜索过程中队列为空，即已经将所有能扩展到的位置全部搜完，此时并没有与另一边会师，说明无解。

需要使用的数据结构

在此过程中需要维护两个队列，用于存放待扩展的字符串，两个方向上各一个

为了保存每个扩展到的字符串的<字符串，到该字符串所用的步数>这个信息，我们需要使用两个哈希表，这样可以快速查询到字符串对应的步数。与队列类似，两个方向上各一个。

注意事项

1. 两边向中间搜索的时候，替换规则是相反的，所以需要两套修改函数

2. 如果出现某一边的搜索量远大于另一边的情况，就会拉低整体的搜索速度，所以我们每次搜索时都找到搜索量较小的一边进行搜索

3. 因为每次替换只能找到最先匹配规则的子串进行修改，如果字符串中存在多个子串能够匹配该规则，则会漏掉除第一个外的全部子串所对应的扩展，所以需要枚举匹配规则时的初始位置，保证每一个能够匹配该规则的子串都能被扩展到

下面给出代码及注释

#include<bits/stdc++.h>
using namespace std;
pair<string,string> rules[6]; // 用于存放规则
unordered_map<string,int> Hash1,Hash2;  // 用于存放字符串及其对应的步骤
string start,End,t;  // 用于记录起点、终点和当前处理的字符串

string modify1(string t,int k,int initpos)
// 第一个修改函数，传入的是待修改的字符串、使用的规则编号、修改时查找的初始位置
{
    int pos=t.find(rules[k].first,initpos); // 找到第一个匹配位置
    if(pos!=string::npos)  // 如果匹配位置存在
    {
        t.erase(pos,rules[k].first.size());  // 清除匹配上的子串
        t.insert(pos,rules[k].second);  // 将替换用的子串插入到字符串的对应位置中
    }
    return t;  // 返回修改后的子串，如果没有修改，就原样返回
}

string modify2(string t,int k,int initpos)
// 与上一个函数相同，只不过调换了规则中两个字符串的位置
{
    int pos=t.find(rules[k].second,initpos);
    if(pos!=string::npos)
    {
        t.erase(pos,rules[k].second.size());
        t.insert(pos,rules[k].first);
    }
    return t;
}

int main(void)
{
    cin>>start>>End;
    int i=0,j,k;
    while(cin>>rules[i].first>>rules[i].second)i++; // 读入规则
    int n=i;

    queue<string> q1,q2;    
    q1.push(start);  // 将开头和结尾先放入队列和哈希表中
    q2.push(End);
    Hash1[start]=0;
    Hash2[End]=0;

    while(!q1.empty()&&!q2.empty())  // 两个队列但凡有一个为空，说明无解
    {
        if(q1.size()<q2.size())  // 找到当前待搜索量较小的一个，进行搜索
        {
            t=q1.front();
            if(Hash2.count(t))break;
            // 如果这个字符串在另一边的搜索中遇到过，说明顺利会师，退出
            q1.pop();
            for(k=0;k<n;k++)
            {
                for(j=0;j<t.size();j++) 
                // 枚举每一种规则和起始位置，防止漏掉可能的扩展
                {
                    string t2=modify1(t,k,j);
                    if(t==t2||Hash1.count(t2))continue;
                    // 如果没有成功更改字符串，说明该规则无法应用于该字符串
                    // 如果这个字符串在之前被处理过了，也不需要再处理了，加上这个
                    // 优化会快很多
                    Hash1[t2]=Hash1[t]+1;
                    q1.push(t2);
                }
            }
        }
        else
        {
            t=q2.front();  // 跟上面一样，处理另一边
            if(Hash1.count(t))break;
            q2.pop();
            for(k=0;k<n;k++)
            {
                for(j=0;j<t.size();j++)
                {
                    string t2=modify2(t,k,j);
                    if(t==t2||Hash2.count(t2))continue;
                    Hash2[t2]=Hash2[t]+1;
                    q2.push(t2);
                }

            }
        }
    }
    if(Hash1[t]+Hash2[t]>10||q1.empty()||q2.empty())puts("NO ANSWER!");
    // 搜索次数大于10或者因队列为空而退出循环都是无解的情况
    else cout<<Hash1[t]+Hash2[t];
    return 0;
}