字串变换

形式化题目

给定两个字符串 $A$ 、 $B$ （长度都不超过 20）和至多 6 条改写规则 $A_i \to B_i$ （规则两侧长度也都不超过 20）。一步变换是指：选取当前串中某一次出现的某个 $A_i$ ，把它替换成对应的 $B_i$ ，得到一个新串。

求从 $A$ 变换到 $B$ 所需的最少步数；若 10 步以内（含 10 步）无法完成，输出 NO ANSWER!。

例如 $A=$ abcd， $B=$ xyz，规则为 abc -> xu、ud -> y、y -> yz，则 abcd -> xud -> xy -> xyz，最少 3 步。

正解

思路

把每个长度不超过 20 的字符串看作图中的一个点，一条规则 $A_i \to B_i$ 在"某次出现恰好是 $A_i$ "的所有位置上各连出一条边。答案就是从 $A$ 到 $B$ 的最短路，边权全是 1，天然应该用 BFS；"10 步以内"这个限制则把整张图限制在深度 10 以内。

先考虑朴素 BFS：从 $A$ 出发，每层把当前串里所有规则的所有出现位置都替换一遍。问题在于每个串的每个位置都可能命中规则，一层扩展能产生的新串数量很大，第 10 层的规模是指数级的，朴素单侧 BFS 很容易在深度较大的数据上爆炸。

双向 BFS 消除这个瓶颈：从 $A$ 和 $B$ 两端各做 BFS。反向那一侧沿的是逆规则 $B_i \to A_i$ ——因为"正向串 $s$ 走一步到 $t$ "等价于"反向串 $t$ 逆着走一步到 $s$ "，两侧扩展出来的距离才能在中间接上。每轮两侧各扩一层，扩到第 $k$ 层时若两侧的已发现集合有交点 $s$ ，则 $dist_A(s) + dist_B(s)$ 就是一条完整路径的长度。

为什么可以在 $dist_A(s) + dist_B(s) \leqslant 2k$ 时直接停：设最短路长度为 $ans \leqslant 2k$ ，在路径上取离 $A$ 端 $\min(k, ans)$ 步的点 $m$ ：

若 $ans \leqslant k$ ，则 $m = B$ ，两侧早已在第一轮就发现了它，交点和会被某一轮统计到；
若 $k < ans \leqslant 2k$ ，则 $dist_A(m) = k \leqslant SIDE\_STEPS$ 且 $dist_B(m) = ans - k \leqslant k$ ，两侧都在前 $k$ 层内发现了 $m$ 。

而 $k$ 层扩展完之后所有距离 $\leqslant k$ 的点都已入队，所以此时枚举交集得到的 $\min(dist_A(s) + dist_B(s))$ 恰等于 $ans$ ——既不遗漏（上面的 $m$ 必在交集中），也不会更小（任何交点都对应一条真实存在的合法路径）。因此每轮扩完就用"交集最小和 $\leqslant 2k$ "作为停止条件，总共只需每侧扩展 5 层，比单侧 BFS 浅一倍。

以样例为例，两侧各扩 2 层就已在 xy 处接上（路径 abcd -> xud -> xy <- xyz， $2 + 1 = 3$ 步）：

flowchart LR
    A["abcd<br/>A侧第0层"] --> S1["xud<br/>A侧第1层"] --> S2["xy<br/>A侧第2层"]
    T["xyz<br/>B侧第0层"] --> S2
    S2 --> S3["3 = 2 + 1"]

$B$ 侧第 1 层能到 xy，靠的是逆规则 $yz \to y$ （xyz 里的 yz 换回 y）；第 2 轮结束时 $A$ 侧也扩到 xy，交集出现，距离和 $2 + 1 = 3 \leqslant 2k = 4$ ，直接返回 3。

两个实现细节：

规则左串在原串中可能重叠出现（如 aaaa 中 a -> b 命中 4 次），找到一个出现后要从下一位继续 find，不能跳过；
两侧分别用 dist 字典兼当 visited 与距离表，队列中串的距离就是字典里存的值，不需要另外编码。

代码

Python 版：

python

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#!/usr/bin/env python3
# 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-10-01 15:25
# update_at: 2026-10-01 15:25

import sys
from collections import deque
from collections.abc import Iterator

SIDE_STEPS = 5  # 双向 BFS 每侧最多扩展的层数，两侧合计覆盖题面的 10 步上限


def expand(source: str, rules: list[tuple[str, str]]) -> Iterator[str]:
    """把 source 中某个规则的左串替换一次，产出所有一步可达的串（可能重复）。"""
    for left, right in rules:
        at = source.find(left)
        while at != -1:
            yield source[:at] + right + source[at + len(left):]
            at = source.find(left, at + 1)  # 从下一位再找，覆盖重叠出现


def layered_bfs(queue: deque[str], dist: dict[str, int], rules: list[tuple[str, str]]) -> None:
    """把 queue 这一侧向外扩展一层：新串的距离 = 队首距离 + 1。"""
    for _ in range(len(queue)):
        source = queue.popleft()
        if dist[source] == SIDE_STEPS:  # 该侧已到层数上限，不再外扩
            continue
        for nxt in expand(source, rules):
            if nxt not in dist:
                dist[nxt] = dist[source] + 1
                queue.append(nxt)


def shortest_steps(start: str, target: str, rules: list[tuple[str, str]]) -> int | None:
    """双向 BFS：返回 A 到 B 的最少变换步数，超过 10 步则返回 None。"""
    if start == target:
        return 0
    back_rules = [(right, left) for left, right in rules]  # 反向侧要沿逆规则走
    side_rules = (rules, back_rules)
    dist = ({start: 0}, {target: 0})  # dist[side]：该侧已发现的串 → 到所属端点的步数
    queues = (deque((start,)), deque((target,)))
    for k in range(1, SIDE_STEPS + 1):
        for side in (0, 1):
            layered_bfs(queues[side], dist[side], side_rules[side])
        # 交点 s 给出一条 A→s→B 的合法路径，两侧距离之和 ≥ 答案；
        # 当和 ≤ 2k 时，最短路的中间点两侧都已在 k 层内发现，该和恰为答案
        best = min((dist[0][s] + dist[1][s]
                    for s in dist[0].keys() & dist[1].keys()), default=None)
        if best is not None and best <= 2 * k:
            return best
    return None


def solve() -> None:
    data = iter(sys.stdin.read().split())
    start = next(data)
    target = next(data)
    rules = []
    for left in data:
        right = next(data)
        rules.append((left, right))  # 变换规则
    steps = shortest_steps(start, target, rules)
    print(steps if steps is not None else "NO ANSWER!")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102/**
 * 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-10-06 17:39
 * update_at: 2026-10-06 17:39
 */
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <climits>

typedef long long ll;

const int SIDE_STEPS = 5; // 双向 BFS 每侧最多扩展的层数，两侧合计覆盖题面的 10 步上限

std::vector<std::pair<std::string, std::string> > rules;      // 正向规则 left -> right
std::vector<std::pair<std::string, std::string> > back_rules; // 反向规则 right -> left，B 侧沿逆规则扩展

std::map<std::string, int> dist_a; // A 侧已发现的串 -> 到 A 的最少步数
std::map<std::string, int> dist_b; // B 侧已发现的串 -> 到 B 的最少步数
std::queue<std::string> qa;        // A 侧待扩展队列
std::queue<std::string> qb;        // B 侧待扩展队列

// 把 q 中当前一层的所有串向 rs 中的规则扩展一层，距离写进 dist。
void extend_layer(std::queue<std::string> &q, std::map<std::string, int> &dist,
                  std::vector<std::pair<std::string, std::string> > &rs) {
    int layer_size = q.size();
    for (int idx = 0; idx < layer_size; idx++) {
        std::string s = q.front();
        q.pop();
        int d = dist[s];
        if (d == SIDE_STEPS) {
            continue; // 该侧已到层数上限，不再向外扩展
        }
        for (int r = 0; r < (int)rs.size(); r++) {
            std::string left = rs[r].first;
            std::string right = rs[r].second;
            // 找 left 在 s 中的每次出现；找到一次后从下一位继续，覆盖重叠出现
            size_t pos = s.find(left, 0);
            while (pos != std::string::npos) {
                std::string nxt = s.substr(0, pos) + right + s.substr(pos + left.size());
                if (dist.find(nxt) == dist.end()) {
                    dist[nxt] = d + 1;
                    q.push(nxt);
                }
                pos = s.find(left, pos + 1);
            }
        }
    }
}

int main() {
    std::string start;
    std::string target;
    if (!(std::cin >> start >> target)) {
        return 0;
    }
    if (start == target) {
        std::cout << 0 << std::endl;
        return 0;
    }
    std::string left;
    std::string right;
    while (std::cin >> left >> right) {
        rules.push_back(std::make_pair(left, right));
        back_rules.push_back(std::make_pair(right, left));
    }

    dist_a[start] = 0;
    qa.push(start);
    dist_b[target] = 0;
    qb.push(target);

    for (int k = 1; k <= SIDE_STEPS; k++) {
        extend_layer(qa, dist_a, rules);
        extend_layer(qb, dist_b, back_rules);

        // 交点 s 给出一条 A -> s -> B 的合法路径，两侧距离之和是一条真实路径长度；
        // 当和 <= 2k 时，最短路的中间点两侧都已在 k 层内发现，该和恰为答案
        int best = INT_MAX;
        std::map<std::string, int>::iterator it;
        for (it = dist_a.begin(); it != dist_a.end(); ++it) {
            std::map<std::string, int>::iterator jt = dist_b.find(it->first);
            if (jt != dist_b.end()) {
                int sum = it->second + jt->second;
                if (sum < best) {
                    best = sum;
                }
            }
        }
        if (best <= 2 * k) {
            std::cout << best << std::endl;
            return 0;
        }
    }

    std::cout << "NO ANSWER!" << std::endl;
    return 0;
}

复杂度

设串长上限 $L = 20$ ，规则数 $R \leqslant 6$ ，每侧扩展深度 $k = 5$ 。每层的状态串数量在最坏情况下按 $R \cdot L$ 的分支因子指数增长，但深度只有 10；双向 BFS 把单侧深度砍半，状态规模从 $b^{10}$ 降到约 $2 b^5$ （ $b$ 为等效分支因子），这正是本题卡时限的关键。单次匹配替换是 $O(L)$ 的，总时间约为 $O(2 b^5 \cdot R \cdot L)$ ，在本题 10 步的深度限制下可以接受；空间同样是两侧已发现串的总量。

图示解析

为什么反向侧要用逆规则

正向规则 $ud \to y$ 表示串里出现 ud 可以换成 y。从 $B$ 端往回找"谁能一步走到我"时，要看的是"哪个串替换一次能得到我"，也就是把 $y$ 换回 $ud$ 。下表用样例的第 2 轮说明两侧如何在 xy 接上：

层数 $k$	A 侧（正向扩展，规则 $A_i \to B_i$ ）	B 侧（逆向扩展，规则 $B_i \to A_i$ ）
0	`abcd`	`xyz`
1	`xud`（`abc` 换成 `xu`）	`udxz`（`y` 换回 `ud`）、`xy`（`yz` 换回 `y`）
2	`xy`（`ud` 换成 `y`）	—— 扩展时发现交集

两侧集合的交集 xy 满足 $dist_A(xy) + dist_B(xy) = 2 + 1 = 3$ ，且 $3 \leqslant 2k = 4$ ，所以 3 就是最少步数。若忘了把反向规则取逆， $B$ 侧扩出来的串全都和正向语义对不上，交集永远为空——这是本题最常见的错误。

总结

本题是"字符串改写"型最短路：串是点、规则的一次命中是一条边，边权为 1，BFS 求最少步数。
深度上限 10 保证答案存在时一定能搜到，但单侧 BFS 第 10 层会指数爆炸；双向 BFS 每侧只扩 5 层，在中间接上，复杂度从 $b^{10}$ 量级降到 $b^5$ 量级。
三个易错点：反向侧必须用逆规则扩展；规则左串的重叠出现要逐位 find 找全；停止条件是"交集最小距离和 $\leqslant 2k$ "而不是"一出现交集就返回"（后者可能错过更短的、中间点还没被两侧同时发现的路径）。
若 10 步内两侧始终没有交点，输出 NO ANSWER!。

目录

形式化题目

正解

思路

代码

复杂度

图示解析

为什么反向侧要用逆规则

总结