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

题意

给定起始串、目标串和若干替换规则。一次操作可把当前串中某次出现的左串替换为右串，求十步以内的最少操作数，否则输出 NO ANSWER!。

思路

把每个字符串看成图上的状态，一次合法替换是一条权值为一的边。要求最少变换次数，因此从起始串 BFS。

对每条规则，用 str.find(old,start) 循环寻找所有出现位置，包括可能重叠的出现；字符串切片构造替换后的新状态。集合 visited 保证同一字符串只入队一次。深度达到十步后不再扩展。

Python 知识

字符串不可变，current[:pos]+new+current[pos+len(old):] 会安全生成新状态。
字符串本身可哈希，可以直接放进 set 判重。
sys.stdin.read().splitlines() 适合读取“首行固定、后续规则直到 EOF”的格式。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：整行字符串与 EOF 输入。
/home/rainboy/mycode/hugo-blog/content/program_language/python/bfs_shortest.md：字符串状态图 BFS。

代码

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
29import sys
from collections import deque


lines = [line.split() for line in sys.stdin.read().splitlines() if line.strip()]
start, target = lines[0]
rules = lines[1:]
queue = deque([(start, 0)])
visited = {start}
answer = None

while queue:
    current, steps = queue.popleft()
    if current == target:
        answer = steps
        break
    if steps == 10:
        continue

    for old, new in rules:
        position = current.find(old)
        while position != -1:
            transformed = current[:position] + new + current[position + len(old):]
            if transformed not in visited:
                visited.add(transformed)
                queue.append((transformed, steps + 1))
            position = current.find(old, position + 1)

print(answer if answer is not None else "NO ANSWER!")

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://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-07-27 00:00
 */

/* P1032 [NOIP 2002 提高组] 字串变换 */
/* BFS 求十步内从起始串到目标串的最少变换次数。 */

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

string start_str, target;
string from[10], to[10]; // 替换规则
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) return cur.step;
        if (cur.step == 10) continue; // 超十步不考虑

        // 尝试每条规则
        for (int r = 0; r < rule_cnt; r++) {
            string& old_s = from[r];
            string& new_s = to[r];
            size_t pos = cur.s.find(old_s);

            // 一个规则可能有多个匹配位置
            while (pos != string::npos) {
                string next = cur.s;
                next.replace(pos, old_s.length(), new_s);

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

                // 继续向后查找
                pos = cur.s.find(old_s, pos + 1);
            }
        }
    }
    return -1; // 不可达
}

int main() {
    cin >> start_str >> target;
    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 个字符串，每个状态枚举规则和出现位置的代价为 T，总时间为 $O(VT)$ ，空间为 $O(V)$ 。

总结

字符串变换的关键是把“当前完整字符串”作为状态。BFS 保证第一次到达目标就是最少步数，十步限制控制搜索深度。

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

目录

题意

思路

Python 知识

代码

复杂度

总结