字串变换

190. 字串变换 - AcWing题库 已知有两个字串 $A$, $B$ 及一组字串变换的规则（至多 $6$ 个规则）:

$A1\to B1$ $A2\to B2$ $\dots$

规则的含义为：在 $A$ 中的子串 $A1$ 可以变换为 $B1$、$A2$ 可以变换为 $B2\dots$。

例如：$A$＝abcd $B$＝xyz

变换规则为：

abc $\to$ xu ud $\to$ y  y $\to$ yz

则此时，$A$ 可以经过一系列的变换变为 $B$，其变换的过程为：

abcd $\to$ xud $\to$ xy $\to$ xyz

共进行了三次变换，使得 $A$ 变换为 $B$。

输入格式

输入格式如下：

A B
A1 B1  
A2 B2  
… …

第一行是两个给定的字符串 $A$ 和 $B$。

接下来若干行，每行描述一组字串变换的规则。

所有字符串长度的上限为 $20$。

输出格式

若在 $10$ 步（包含 $10$ 步）以内能将 $A$ 变换为 $B$ ，则输出最少的变换步数；否则输出 NO ANSWER!。

输入样例：

abcd xyz
abc xu
ud y
y yz

输出样例：

3

思路

给一个串A, 和6个变换规则, 求变化到B串要用的最少步数。

应用一个规则时, 需要枚举串A, 找到可以应用的点, 然后应用。因此, 最坏情况下, 长度为20的A串, 每个位置都能应用6个规则, 搜10次的话为 $(20\times 6{)}^{10}=120^{10}$ 。不过肯定不会都能应用, 可以只考虑规则数, 时间复杂度为 $6^{10}$, 这同样还是太高了。

需要进行优化, 这里采用双向BFS的方法, 将时间复杂度优化到 $2\times 6^5=15552$, 很舒服。 双向BFS过程为： 定义俩队列qa qb, qa为从起点开始的BFS, qb为从终点开始的BFS。 每次扩展时优先扩展队列长度小的。

该题扩展时需要枚举当前字符串所有位置, 然后再枚举规则进行应用, 若新得出的串未被该方向上的哈希表标记, 则加入队列并标记。 若已被另一个方向的哈希表标记, 说明搜索相遇, 当前路径就是最小路径, 输出答案即可。 若扩展时有一个队列为空, 说明起点和中间不存在通路, 直接返回无解。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <unordered_map>
using namespace std;
const int N = 6;
int n;
string a[N], b[N];
int temp;
 
int extend(queue<string> &q, unordered_map<string, int> &da, unordered_map<string,int> &db, string a[], string b[])
{
    string t = q.front();
    q.pop();
    
    for(int i = 0; i < t.size(); i++)
        for(int j = 0; j < 6; 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(db.count(state)) return da[t] + db[state] + 1;
                if(da.count(state)) continue;
                q.push(state);
                da[state] = da[t] + 1;
            }
        }
    return 11;
}
 
int bfs(string A, string B)
{
    if(A == B) return 0;
    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 = 11;
        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 cout << step << endl;
    return 0;
}