[NOIP 2002 提高组] 字串变换（疑似错题）

形式化题目

给定两个字符串 $A$ 、 $B$ 和至多 6 条替换规则（子串对 $(A_i, B_i)$ ）。一步操作是：选出当前串中等于某个 $A_i$ 的一处子串，把它替换成对应的 $B_i$ （每次只替换一处）。问从 $A$ 变换到 $B$ 至少需要几步；若 10 步以内（含 10 步）无法完成，则无解。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-13 13:29
 * update_at: 2026-08-13 13:35
 */
/* P1032 字串变换 */
/* brute.cpp：小数据暴力解，把每一步操作看成选择序列来递归枚举。 */
/* 每层递归选择一个决策：(用哪条规则, 替换哪个出现位置)，深度限制在 10 步。 */

#include <bits/stdc++.h>
using namespace std;

const int MAX_STEP = 10; // 题目要求十步以内（含十步）

string start_str, target_str; // 起始串与目标串
string from[10], to[10];      // 变换规则
int rule_cnt;                 // 规则数量

int best = MAX_STEP + 1; // best 记录当前找到的最少步数，MAX_STEP+1 表示无解

int choose_step[MAX_STEP + 1]; // 第 dep 步选择用哪条规则
int choose_pos[MAX_STEP + 1];  // 第 dep 步替换的是哪个出现位置

set<pair<string, int> > vis; // 判重：(当前串, 已用步数) 相同就无需再搜

// dfs(dep, s)：当前已经变换了 dep 步，当前串是 s。
// 这一层在枚举第 dep+1 步的决策：某条规则 + 它在 s 中的一个出现位置。
void dfs(int dep, string s) {
    if (s == target_str) {
        if (dep < best) best = dep; // 到达目标，记录所用步数
        return;
    }
    if (dep == MAX_STEP || dep >= best)
        return; // 达到步数上限或不可能更优

    // 同样步数下到达同一个串，之前已经搜过，直接跳过
    pair<string, int> key = make_pair(s, dep);
    if (vis.find(key) != vis.end())
        return;
    vis.insert(key);

    // 枚举第 dep+1 步的决策
    for (int r = 0; r < rule_cnt; r++) {
        int flen = from[r].size();

        // 枚举规则 r 在当前串 s 中的所有出现位置
        size_t pos = s.find(from[r]);
        while (pos != string::npos) {
            choose_step[dep + 1] = r;
            choose_pos[dep + 1] = (int)pos;

            string next_s = s.substr(0, pos) + to[r]
                          + s.substr(pos + flen);
            dfs(dep + 1, next_s);

            // 从下一个位置继续找，覆盖重叠出现
            pos = s.find(from[r], pos + 1);
        }
    }
}

int main() {
    cin >> start_str >> target_str;

    // 规则行读到 EOF 结束
    string a, b;
    while (cin >> a >> b) {
        from[rule_cnt] = a;
        to[rule_cnt] = b;
        rule_cnt++;
    }

    dfs(0, start_str);

    if (best == MAX_STEP + 1)
        cout << "NO ANSWER!\n";
    else
        cout << best << "\n";

    return 0;
}

这个暴力把问题看成一条“操作选择序列”：每层递归在枚举下一步用哪条规则、替换当前串中的哪个出现位置（choose_step[]、choose_pos[] 记录完整决策），深度限制在 10 步；到达目标串时用当前步数更新最优值。(当前串, 已用步数) 的判重集合是给递归减负的最小记忆化——同样步数到达同一个串，后面可做的选择完全一样，不用重复搜。

它的瓶颈在于按路径枚举：同一个状态可能被多条不同顺序的路径反复到达，十步内路径组合的数量可以爆炸。

关键观察是把问题看成隐式图最短路：

状态就是字符串本身，一次替换就是一条权值为 1 的边；
边权全为 1 的无权图求最短路用 BFS：按层扩展，第一次到达目标串时所用的步数就是最少步数；
BFS 里判重只按字符串做即可：第一次到达某串时已经是最少步数，之后到达一律跳过；
一条规则可能在当前串中出现多处（包括重叠出现，如 aaa 中的 aa），每一处都是独立的后继状态，都要枚举。

以样例为例，从 abcd 到 xyz 的三步变换（每次只替换一处出现）：

步	当前串	使用的规则（出现位置）	结果串
0	`abcd`	无	`abcd`
1	`abcd`	`abc -> xu`（位置 0）	`xud`
2	`xud`	`ud -> y`（位置 1）	`xy`
3	`xy`	`y -> yz`（位置 0）	`xyz`

观察这 4 行：每一步只替换一处子串，串长可以变化；abc 只出现在 abcd 的位置 0，但一般规则会有多个命中位置，BFS 必须把每一处都展开成后继状态。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-08-13 13:35
 */
/* P1032 [NOIP 2002 提高组] 字串变换 */
/* BFS：把字符串看成状态，一次替换是一条边，求十步内到目标串的最少步数。 */

#include <bits/stdc++.h>
using namespace std;

string start_str, target_str; // 起始串与目标串
string from[10], to[10];      // 变换规则：子串 from[i] 可以替换成 to[i]
int rule_cnt;                 // 规则数量

// BFS 队列元素：当前字符串和已经用的步数。
struct Node {
    string s;
    int step;
};

int bfs() {
    queue<Node> q;
    set<string> vis; // 判重：同一个字符串只需要访问一次
    q.push({start_str, 0});
    vis.insert(start_str);

    while (!q.empty()) {
        Node cur = q.front();
        q.pop();

        if (cur.s == target_str)
            return cur.step; // BFS 第一次到达目标就是最少步数

        if (cur.step == 10)
            continue; // 十步以内（含十步）才允许继续变换

        // 尝试每一条规则
        for (int r = 0; r < rule_cnt; r++) {
            int flen = from[r].size();

            // 一条规则可能在当前串中出现多个位置，逐个替换
            size_t pos = cur.s.find(from[r]);
            while (pos != string::npos) {
                string next_s = cur.s.substr(0, pos) + to[r]
                              + cur.s.substr(pos + flen);

                if (vis.find(next_s) == vis.end()) {
                    vis.insert(next_s);
                    q.push({next_s, cur.step + 1});
                }

                // 从下一个位置继续找，避免漏掉重叠的出现
                pos = cur.s.find(from[r], pos + 1);
            }
        }
    }
    return -1; // 十步内不可达
}

int main() {
    cin >> start_str >> target_str;

    // 规则行读到 EOF 结束
    string a, b;
    while (cin >> a >> b) {
        from[rule_cnt] = a;
        to[rule_cnt] = b;
        rule_cnt++;
    }

    int ans = bfs();
    if (ans == -1)
        cout << "NO ANSWER!\n";
    else
        cout << ans << "\n";

    return 0;
}

复杂度

设十步内实际访问到的不同字符串数量为 $V$ ，每个状态要枚举全部规则和当前串中的全部出现位置，并做一次 set 判重；字符串长度上限为 20，但替换可能让串变长。总时间 $O(V \cdot (rL + L\log V))$ ，空间 $O(VL)$ ，其中 $r$ 是规则数、 $L$ 是串长。

需要指出： $V$ 本身最坏可以随深度指数增长，所以本题并没有多项式复杂度的保证——这是洛谷标注“疑似错题”的原因，官方数据很水，普通 BFS 就能通过。

总结

字符串变换题的关键是把“当前完整字符串”当成状态、把一次替换当成一条边：这样“最少变换步数”就变成了无权图最短路，BFS 的层扩展天然保证第一次到达目标就是答案。实现上注意三点：每条规则的所有出现位置（含重叠）都要枚举、每个字符串只入队一次、到达第 10 步不再扩展。这套“隐式图 BFS + 状态判重”的模型与 rbook 的《图的遍历》中的 BFS 思想一致。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19朴素解（brute.cpp）
  DFS 枚举操作选择序列：每层选 (规则, 出现位置)，深度 ≤ 10
  (串, 步数) 判重集合减负
        |
        | 瓶颈：按路径枚举，同一状态被多条路径反复到达
        v
关键观察
  字符串 = 状态，一次替换 = 权为 1 的边
  无权图最短路 -> BFS 分层扩展
  第一次到达某串就是最少步数 -> 只需按字符串判重
        |
        v
BFS（main.cpp）
  队列存 (当前串, 步数)，set 判重
  每条规则枚举全部出现位置（find + pos+1，含重叠）
  出队命中目标返回步数；step == 10 不再扩展
        |
        v
  命中：最少步数 / 队列空：NO ANSWER!

图中三条主线分别对应“暴力枚举了什么”“观察到什么性质”“正式解如何利用这个性质”。BFS 相比 DFS 选择序列的本质改进，是把判重从“路径上的 (串, 步数)”收紧成“按串判重”，因为分层扩展保证第一次到达就是最优。