AcWing 190. 字串变换

目录：算法日记

题目来源：190. 字串变换 – AcWing题库

题目描述

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

$A1→B1$

$A2→B2$

$…$

规则的含义为：在 $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$
$A1 B1$
$A2 B2$
$… …$

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

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

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

输出格式

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

输入样例：

abcd xyz
abc xu
ud y
y yz
复制代码

输出样例：

3
复制代码

算法思路

字符串变换规则最多$6$种，求最少变换次数，标准最短路模型。虽然字符串变换规则有$6$种，但可转移的状态数量可能远大于$6$种。例如，若存在规则ab->a与ba->b，则对于形如...ababa...的序列，由于存在ab与ba的交替重复出现，显著增加了计算的复杂度。即使在题目要求$10$步以内才是有效答案，时间复杂度也高达$O(N^{10})$，其中$N$为可扩展状态数。因此引入双向BFS进行优化，初状态与末状态同时BFS，判断是否存在相同的中间状态，时间复杂度可降到$O(2N^5)$。

在进行双向BFS的过程中，可进一步进行优化，优先扩展队列长度较短一侧状态。针对本题需要考虑边界：

1. 一侧的队列先空，则说明出状态与末状态见不可达；
2. 总遍历次数大于$10$，则说明不存在$10$步内的可行解；
3. 每次BFS需遍历一层状态；

针对第$3$点，需做特殊说明，如下图所示：

当一侧BFS按状态$A、B、C$顺序进行入队时，若不按层遍历，则转换经历状态$A、G、D$共进行$4$次操作，此时，该解的操作次数小于$10$，是一个可行解，但不一定满足最优解。上图中，最优解经历状态$C、F$，仅需进行$3$次操作。

AC代码

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
int n = 0;

int extend(queue<string>& q, map<string, int>& da, map<string, int>& db, string ra[], string rb[]) {
    int d = da[q.front()];
    while(!q.empty() && da[q.front()] == d) {
        string cur = q.front();
        q.pop();
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < cur.size(); ++j) {
                if(cur.substr(j, ra[i].size()) == ra[i]) {
                    string r = cur.substr(0, j) + rb[i] + cur.substr(j + ra[i].size());
                    if(db.count(r)) return db[r] + 1 + da[cur];
                    if(da.count(r)) continue;
                    da[r] = da[cur] + 1;
                    q.push(r);
                }
            }
        }
    }
    return 11;
}

int bfs(string a, string b, string ra[], string rb[]) {
    if(a == b) return 0;
    map<string, int> da, db;
    queue<string> qa, qb;
    
    qa.push(a);
    da[a] = 0;
    qb.push(b);
    db[b] = 0;
    
    int step = 0;
    while(!qa.empty() && !qb.empty()) {
        int t = 0;
        if(qa.size() < qb.size()) t = extend(qa, da, db, ra, rb);
        else t = extend(qb, db, da, rb, ra);
        
        if(t <= 10) return t;
        if(++step == 10) return -1; 
    }
    return -1;
}

int main() {
    string a, b;
    string ra[6], rb[6];
    cin>>a>>b;
    while(cin>>ra[n], cin>>rb[n]) n++;
    int t = bfs(a, b, ra, rb);
    if(t == -1) cout<<"NO ANSWER!"<<endl;
    else cout<<t<<endl;
    return 0;
}
复制代码