题目描述

已知有两个字串A,B及一组字串变换的规则（至多6个规则）:
A1 -> B1
A2 -> B2
规则的含义为：在 A中的子串 A1 可以变换为B1​，A2可以变换为B2​ …。
例如 A="abcd",B="xyz",
变换规则为:
abc → xu,ud → y,y → yz
则此时，A可以经过一系列的变换变为B，其变换的过程为：
abcd → xud → xy → xyz。
共进行了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;
}