洛谷P1032《字串变换》

十月 30, 2018 3486

NO ANSWER!

题目描述

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

A_1 \rightarrow B_1

A_2 \rightarrow B_2
​
规则的含义为：在 A 中的子串 A_1 可以变换为 B_1 ， A_2 可以变换为 B_2 \dots

例如： A= ’ abcdabcd ’， B＝ ’ xyzxyz ’

变换规则为：

‘ abc ’ \rightarrow ‘ xu ’

‘ ud ’ \rightarrow ‘ y ’

‘ y ’ \rightarrow ‘ yz ’

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

‘ abcd ’ \rightarrow ‘ xud ’ \rightarrow ‘ xy ’ \rightarrow ‘ xyz ’

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

Input / Output 格式 & 样例

输入格式：

输入格式如下：

A B

A_1 B_1
​
A_2 B_2 ​ |\rightarrow 变换规则

… … /

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

输出格式：

输出至屏幕。格式如下：

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

输入样例

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

输出样例

1
3

解题思路

这是一个 BFS

题目刚上来就有一个坑

输入不给行数 只知道最多六行

于是我们用一个变量l来记录输入的行数

我这里选择用A[0]和B[0]来存两个原字符串

首先如果l == 0而且A[0] != B[0]，那直接输出NO ANSWER!

否则用一个变量v来记录BFS()的返回值

如何搜索？

www.baidu.com

我们建两个队列q和step，分别存需要修改的字符串和这个字符串所对应的步数

循环的时候就不能只判!q.empty()，还要判q.front() != B[0] /* 字符串还需要修改 */和step.front() <= 10 /* 限制只能修改10次 */

我们还需要用一个map<string, bool>来判重

剩下的一些解释我直接扔到代码注释里面了

代码实现

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
using namespace std;

const int MAXN = 6 + 3;

map<string, bool> KangShifu;
string A[MAXN], B[MAXN];

int BoynextdoorFaqSearch(int l) {
    int ans = 0;
    queue<string> q;
    queue<int> step;
    q.push(A[0]);
    step.push(0);
    while (!q.empty() && q.front() != B[0] && step.front() <= 10) {
        if (KangShifu[q.front()]) {
            q.pop();
            step.pop();
            continue;
            // 去重
        }
        KangShifu[q.front()] = true;
        for (int i = 1; i <= l; ++i) {
            string s = q.front(); // 用一个string记录下当前需要修改的字符串
            while (true) {
            	// 可能不止修改一次
                int loc = s.find(A[i]);
                if (loc == -1) break;
                // 并没有找到
                string ss = q.front();
                // 再复制一份需要修改的字符串
                ss.replace(loc, A[i].size(), B[i]);
                // 修改
                q.push(ss);
                // 把它扔进队列
                step.push(step.front() + 1);
                // 步骤数 + 1
                s[loc] = '~';
                // 把这个能搜到的地方用一个无关紧要的放起来
                // 防止下次还能被搜到
            }
        }
        q.pop();
        step.pop();
        // 处理完毕
    }
    if (q.empty() || step.front() > 10) ans = -1;
    // 如果队列空了或超过10步了，输出NO ANSWER!
    else ans = step.front();
    // 否则输出真正的答案
    return ans;
}

int main(int argc, const char * argv[]) {
    int l = 0;
    while (cin >> A[l] >> B[l]) ++l;
    --l;
    if (l == 0 && A[0] != B[0]) puts("NO ANSWER!");
    else {
        int v = BoynextdoorFaqSearch(l);
        // Boy Next Door
        if (v == -1) puts("NO ANSWER!");
        else cout << v << endl;
    }
    return 0;
}