P1032 [NOIP2002 提高组] 字串变换——dfs、bfs

[NOIP2002 提高组] 字串变换

题目背景

本题疑似错题，不保证存在靠谱的多项式复杂度的做法。测试数据非常的水，各种做法都可以通过，不代表算法正确。因此本题题目和数据仅供参考。

题目描述

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

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

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

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

变换规则为：

• $\text{abc}\to \text{xu}$，$\text{ud}\to \text{y}$，$\text{y}\to \text{yz}$。

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

• $\text{abcd}\to \text{xud}\to \text{xy}\to \text{xyz}$。

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

abcd xyz
abc xu
ud y
y yz
1
2
3
4

样例输出 #1

3
1

提示

对于 $100\%$ 数据，保证所有字符串长度的上限为 $20$。

【题目来源】

NOIP 2002 提高组第二题

分析

1. 一开始直接用dfs写的，后两个点超时了，后来换的bfs，两个思路一样，最短路问题还带是bfs；
2. 需要注意替换的不一定是最开始匹配的子串，替换的还可能是后面的子串，比如这组样例：abcdeabcd abcdee
   abcd e
   替换的是后面那个abcd，所以我们在枚举某个替换规则时，我们要用一个while循环，配合着find函数第二个参数，从上一个子串的下一位置idx + 1寻找，避免一直找的是第一个（ss.find(s[i].first, idx + 1)）；
3. 此题关键在于字符串的处理，以及find函数、replace函数的使用，而且用replace时候，记着用一个临时变量ss保存下，对临时变量修改，不能直接对当前队列头部的字符串直接replace，不然影响下一条替换队则；
   
   

bfs（AC）

#include

using namespace std;

struct node {
    string str;
    int step;

    node(string ss, int ste) {
        str = ss, step = ste;
    }
};

string a, b;
pair<string, string> s[10];
int cnt, ans = 1000000;
queue<node> q;

void bfs() {
    while (!q.empty()) {
        node now = q.front();
        q.pop();
        if (now.step > 10)
            continue;
        if (now.str == b) {
            ans = now.step;
        }
        for (int i = 0; i < cnt; i++) {
            //子串可能存在多个，分别替换每一个
            int idx = -1;
            while (1) {
                string ss = now.str;//不能直接对now.str进行replace等修改
                //从上一个子串的下一位置idx + 1寻找，避免一直找的是第一个
                idx = ss.find(s[i].first, idx + 1);
                if (idx == -1)
                    break;
                ss.replace(idx, s[i].first.size(), s[i].second);
                if (ss == b) {
                    ans = now.step + 1;
                    return;
                }
                q.push(node(ss, now.step + 1));
            }
        }
    }
}

int main() {
    cin >> a >> b;
    while (cin >> s[cnt].first && cin >> s[cnt++].second);
    q.push(node(a, 0));
    bfs();
    if (ans != 1000000)
        cout << ans;
    else
        cout << "NO ANSWER!";
    return 0;
}

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

dfs（TLE）

#include

using namespace std;

string a, b;
pair<string, string> s[10];
int cnt, ans = 1000000;

void dfs(string str, int step) {
    if (step > ans || step > 10)
        return;
    if (str == b) {
        ans = min(ans, step);
        return;
    }
    for (int i = 0; i < cnt; i++) {
        //子串可能存在多个，分别替换每一个，分别dfs
        int idx = -1;
        while (1) {
            string ss = str;
            //从上一个子串的下一位置寻找，避免一直找的是第一个
            idx = ss.find(s[i].first, idx + 1);
            if (idx == -1)
                break;
            ss.replace(idx, s[i].first.size(), s[i].second);
            dfs(ss, step + 1);
        }
    }
}

int main() {
    cin >> a >> b;
    while (cin >> s[cnt].first && cin >> s[cnt++].second);
    dfs(a, 0);
    if (ans != 1000000)
        cout << ans;
    else
        cout << "NO ANSWER!";
    return 0;
}

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