python/TangDou/AcWing/TwoWaySearch/190.md

AcWing 190. 字串变换

一、题目描述

已知有两个字串 A, B 及一组 字串变换的规则（至多 6 个规则）: A_1→B_1 A_2→B_2 …

规则的含义为：在 A 中的子串 A_1 可以变换为 B_1、A_2 可以变换为 B_2…。

例如：A＝abcd B＝xyz

变换规则为：

abc → xu ud → y y → yz

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

abcd → xud → xy → xyz

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

输入格式 输入格式如下：

A ~ B A_1 ~ B_1 A_2 ~ B_2 … …

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

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

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

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

输入样例：

abcd xyz
abc xu
ud y
y yz

输出样例：

3

二、题目解析

bfs的扩展方式

• 枚举在原字符串中使用替换规则的起点
• 枚举所使用的的替换规则

很明显是 最小步数模型，我们先来分析一下单向起点开始bfs：

假设每次决策数量是 K，那么如果 直接bfs ，第一层是1,第二层是K，第三层是K*K=K^2,如果走十步，最坏情况下的搜索空间是 K^{10}，非常大，所以会TLE或者MLE。现在K<=6,那极限就是6^{10}=60466176,字符串大小上限为20,就是再乘上一个20=60466176 \times 20 = 1209323520 ~byte = 1180980 kb=1153mb

如果采用 双向bfs，则可以把 搜索空间 降到 2 \times K^5。在实际测试中只需 20ms 左右，剪枝效果很好。

双向bfs

在双向bfs时，每次选择队列中元素数量较少的方向来扩展。

总结

• 一边扩展完了另一边还能扩展，说明不连通，达不到终状态
• 在枚举能替换的状态的时候用substr函数可以方便很多
• 写代码的时候压入队列扩展写一份即可，从起点扩展的方式和从终点扩展的方式是反过来的，一个是a变化到b,一个是变化b变化到a。

三、普通bfs

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

const int N = 10;
string a[N], b[N];          // 规则串，a[i]->b[i]
string A, B;                // 原始串
queue<pair<string, int>> q; // bfs专用队列
unordered_set<string> st;   // 是不是出现过

int n;

int bfs() {
    q.push({A, 0}); // 字符串，变换次数
    st.insert(A);   // A串出现过

    while (q.size()) {
        auto u = q.front();
        q.pop();

        string t = u.first;
        int d = u.second;
        if (t == B) return d; // 找到，返回路径长度

        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 ts = t.substr(0, i) + b[j] + t.substr(i + a[j].size());
                    if (st.count(ts) == 0) {
                        q.push({ts, d + 1});
                        st.insert(ts);
                    }
                }
            }
        }
    }
    return INF;
}

// 通过了 9/10个数据
// 最后一个测试点挂掉
// 简单暴搜：超时
int main() {
    cin >> A >> B;
    while (cin >> a[n] >> b[n]) n++;
    int ans = bfs();
    if (ans > 10)
        puts("NO ANSWER!");
    else
        printf("%d\n", ans);
    return 0;
}

四、双向广搜

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10;
string A, B;       // 原始串
string a[N], b[N]; // 规则

queue<string> qa, qb;              // 双端队列
unordered_map<string, int> da, db; // 此字符串，是几步转移过来的
int n;

int bfs() {
    // 两个串分别入队列
    qa.push(A), qb.push(B);
    da[A] = 0, db[B] = 0;

    // 双向广搜套路
    while (qa.size() && qb.size()) {
        // 1、从qa中取
        string u = qa.front();
        qa.pop();
        // 如果在b的扩展中出现过，则距离相加
        if (db.count(u)) return da[u] + db[u];

        for (int i = 0; i < u.size(); i++) // 枚举字符串的每一位
            for (int j = 0; j < n; j++) {  // 枚举规则
                if (u.substr(i, a[j].size()) == a[j]) {
                    string ts = u.substr(0, i) + b[j] + u.substr(i + a[j].size());
                    if (!da.count(ts)) {
                        qa.push(ts);
                        da[ts] = da[u] + 1;
                    }
                }
            }

        // 2、从qb中取
        u = qb.front();
        qb.pop();
        if (da.count(u)) return da[u] + db[u];
        for (int i = 0; i < u.size(); i++)
            for (int j = 0; j < n; j++) {
                if (u.substr(i, b[j].size()) == b[j]) {
                    string ts = u.substr(0, i) + a[j] + u.substr(i + b[j].size());
                    if (!db.count(ts)) {
                        qb.push(ts);
                        db[ts] = db[u] + 1;
                    }
                }
            }
    }
    return INF;
}

// 可以AC掉本题,16ms
int main() {
    cin >> A >> B;
    while (cin >> a[n] >> b[n]) n++;

    int ans = bfs();
    if (ans > 10)
        puts("NO ANSWER!");
    else
        printf("%d\n", ans);
    return 0;
}