P1032-字串变换

题目描述

已知有两个字串A,B及一组字串变换的规则(至多6个规则):
A1 -> B1
A2 -> B2
规则的含义为:在 A中的子串 A1 可以变换为B1​,A2可以变换为B2​ …。
例如 A="abcd",B="xyz",
变换规则为:
abcxu,udy,yyz
则此时,A可以经过一系列的变换变为B,其变换的过程为:
abcdxudxyxyz
共进行了3次变换,使得A变换为B。

输入格式

输入格式如下:
A B
A1 B1
A2​ B2​ |-> 变换规则
... ... /
所有字符串长度的上限为20。

输出格式

输出至屏幕。格式如下:

若在10步(包含10步)以内能将A变换为B,则输出最少的变换步数;否则输出"NO ANSWER!"

输入输出样例

输入
abcd xyz
abc xu
ud y
y yz
输出
3

思路

当看到'输出最少的变换步数',就想到适合用bfs来解决,这题用bfs解决的原理是:先把最初的字符串A串装入队列中,然后依次从队列中取出元素,每次取出元素,都把它可以变换的字符串再装入队列中(比如例题中取出了abcd,就把xud装入队列),当某次装入的字符串正好等于目标字符串B串时,那么它的变换次数就是最少步数,如果队列为空都变换不到B串,则说明A串无法变换为B串。
不过有些需要注意的是:
每个变换规则对每个取出的字符串不一定只用一次,比如字符串为abcabc,变换规则有abc->xu,那么正确的做法是把xuabc和abcxu都装入队列,所以应该用循环来做查找abc而不是只找一次。
需要一个容器记录装入过队列的字符串,当变换的字符串曾经入队过,就不再入队,否则入队并且记录该字符串,这样是为了保证第一次变换出的B串的变换次数就是最少次且不会出现ab变ac,ac又变ab的死循环。由此可见,这个容器需要装入不重复的元素且提供查找元素函数,所以用set容器就很适合。

源码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<set>

using namespace std;

string keys[7], values[7];
int n;            //规则个数
struct Element {      //也可以用pair,个人觉得结构体方便些
    string str;        //当前字符串
    int n;                //变换次数
};
queue< Element > que;
set<string> seen;        //出现过的字符串
string a, b;        //初始字符串和目标字符串
int bfs() {
    seen.insert(a);
    que.push({ a,0 });
    while (que.empty() == false) {
        Element tmpEle = que.front();
        que.pop();
        for (int j = 0; j < n; j++) {
            int findIdx = -1;
            //从第0/上一次匹配位置findIdx 开始查找第j个key
            while ((findIdx = tmpEle.str.find(keys[j], findIdx + 1)) != string::npos) {
                string str = tmpEle.str;
                str.replace(findIdx, keys[j].length(), values[j]);        //把字符串中当前查找到的key替换成value
                if (seen.find(str) == seen.end()) {        //如果没有出现过这个字符串
                    if (str == b || tmpEle.n + 1 > 11)return tmpEle.n + 1;
                    que.push({ str,tmpEle.n + 1 });
                    seen.insert(str);
                }
            }
        }
    }
    return 11;
}

int main() {
    cin >> a >> b;
    while (cin >> keys[n] >> values[n])
        n++;
    int sum = a == b ? 0 : bfs();
    if (sum <= 10)cout << sum << endl;
    else cout << "NO ANSWER!" << endl;

    return 0;
}
本文作者:六月丶

本文链接:https://hctra.cn/index.php/archives/437/

版权声明:如无特别声明,本文即为六月'blog原创,仅代表个人观点,如要转载请务必注明文章出处。
最后修改:2019 年 11 月 27 日 03 : 35 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论