ACWing 190 字串变换题解

y0k1n0

2025 年 02 月 26 日

23 次浏览

暂无评论

2340字数

搜索

# 题目描述

已知有两个字串 $A,B$ 及一组字串变换的规则（至多 $6$ 个规则），形如：

- $A_1\to B_1$。
- $A_2\to B_2$。

规则的含义为：在 $A$ 中的子串 $A_1$ 可以变换为 $ B_1$，$A_2$ 可以变换为 $B_2\cdots$。

例如：$A=\texttt{abcd}$，$B＝\texttt{xyz}$，

变换规则为：

- $\texttt{abc}\rightarrow\texttt{xu}$，$\texttt{ud}\rightarrow\texttt{y}$，$\texttt{y}\rightarrow\texttt{yz}$。

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

- $\texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz}$。

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

# 输入

第一行有两个字符串 $A,B$。

接下来若干行，每行有两个字符串 $A_i,B_i$，表示一条变换规则。

# 输出

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

# 解题思路

本题可以考虑bfs做法， 对于传统的bfs做法， 假设每一个字符串对于每一个字符最多可以发生一次替换， 十次替换内总的广搜次数为$6^{10}=60466176$, 因此暴力不可取。

下面考虑对于传统的暴力做法进行优化， 考虑**从开始字符串正向搜索和从答案字符串逆向搜索同时进行**，显然，如果两个队列中同时搜索到了某一个字符串，则所用的步数为最小步数。

**小小的优化**：

- 在每一次拓展节点的时候， 一次拓展队列中的一层节点， 即将队列中所有的和队头深度相同的节点一同拓展， 这样子可以减少重复节点的拓展，  提高搜索效率
- 每次拓展时， 选择两个队列中元素较少的队列拓展， 这样节省空间且搜索更快

# AC代码

```cpp
#include<cstdio>
#include<iostream>
#include<unordered_map>
#include<cstring>
#include<queue>
using namespace std;
const int N = 6;

int cnt;
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.size() && da[q.front()] == d)//保证只更新同一层的节点
    {
        string t = q.front();
        q.pop();
        for (int i = 0; i < cnt; i ++)
        {
            for (int j = 0; j < t.size(); j ++)
            {
                if(t.substr(j, a[i].size()) == a[i])
                {
                    string ans = t.substr(0, j) + b[i] + t.substr(j + a[i].size());
                    if(db.count(ans))
                        return da[t] + 1 + db[ans];
                    if(da.count(ans))
                        continue;

da[ans] = da[t] + 1;
                    q.push(ans);
                }
            }
        }
    }
    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;

int cnt = 0;

while(qa.size() && qb.size())
    {
        cnt++;
        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(cnt > 10)
            return -1;
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> A >> B;
    while(cin >> a[cnt] >> b[cnt])
        cnt++;

int t = bfs(A, B);
    if(t == -1)
        cout << "NO ANSWER!";
    else
        cout << t << endl;
}
```

最后修改：2025 年 02 月 26 日