洛谷 P1032 [NOIP 2002 提高组] 字串变换

本题采用双向 BFS 来解决。

首先分析一下时间复杂度：变换规则数 $R \leq 6$ ，字符串长度 $L \leq 20$，操作数在 10 次以内，用朴素 BFS 的时间复杂度为 $O((L\cdot R)^{10})$ ，完全爆炸；采用双向 BFS 的时间复杂度为 $O((L\cdot R)^{5})$ ，相对于朴素做法降低了很多的时间复杂度。

但对于本题，可能出现以下情况：每次变换可能在字符串的多个位置替换、变换规则可能形成“无限繁殖”的状态等，导致搜索空间飞速增长。双向 BFS 并不能保证通过本题的数据，但也是一种优化搜索的方法。

双向 BFS 的具体步骤：

• 开两个队列 $qa,qb$，一开始分别把起点和终点丢入队列中。
• 每次选择较小的队列进行扩展，将队头其可能经过变换规则得到的字符串丢入队列中（注意假如扩展 $qb$ ，那么需要将规则反向）。扩展的时候注意判断：假如扩展后的字符串在本队列中，则不用入队；若在另外一个队列中，说明双向搜索会合了，直接返回距离之和即可；否则更新一下距离并入队。
• 若一直没有会合，说明没有找到。

以扩展 $qa$ 为例，设 $da[i],db[i]$ 为状态 $i$ 在 $qa,qb$ 中的操作数，假如发现扩展后的字符串在 $qb$ 中出现过，则直接返回 $da[i]+db[j]+1$ ，其中 $j$ 是由状态 $i$ 扩展得到的新状态。

我使用 unordered_map 处理映射关系，具体代码见下：

#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()];
    while(!q.empty() && 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> qa,qb;
    unordered_map<string,int> da,db;
    qa.push(A);qb.push(B);
    da[A] = db[B] = 0;
    int step = 0;
    while(!qa.empty() && !qb.empty())
    {
        int t;
        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;
        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;
}