洛谷题单指南-搜索-P1032 [NOIP2002 提高组] 字串变换

原题链接：https://www.luogu.com.cn/problem/P1032

题意解读：要计算子串变换的最少步数，典型的最短路问题，可以通过BFS求解。

解题思路：

思路上比较直观，从给定的字符串开始，找有多少种替换可能，依次进行替换，存入队列，继续BFS，过程中记录替换的次数

但是，有一些细节还需要注意：

1、有多种替换规则，需要逐条尝试

2、对于每一种替换规则，可能有多处可以替换，也需要逐个位置尝试

3、因此每一个替换规则的每一处替换位置，才产生依次替换

其他就是BFS过程中的常规代码。

100分代码：

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

string a, b;
string src[10], dest[10]; //替换规则：src是寻找的子串，dest是替换的子串
int cnt; //规则数

map<string, bool> flag; //字符串是否出现过
map<string, int> depth; //字符串是经过几次变换来的，也就是路径长度

queue<string> q;

bool bfs(string a)
{
    q.push(a);
    flag[a] = true;
    while(q.size())
    {
        string cur = q.front(); q.pop();
        
        for(int i = 0; i < cnt; i++) //遍历所有替换规则
        {
            int pos = 0;
            vector<int> allpos; //存储包含子串的所有位置，可以替换任意一个
            while(pos < cur.size()) //不断在字符串中找子串，如果找到就在后面继续找，所有子串都要替换掉
            {
                pos = cur.find(src[i], pos); //从pos位置开始找r.first子串
                if(pos >= 0 && pos < cur.size()) //如果找到子串
                {
                    allpos.push_back(pos); //记录子串位置
                    pos += src[i].size(); //寻找的位置移动跳过子串
                }
                else break;
            } 

            for(int j = 0; j < allpos.size(); j++) //对不同位置的子串进行替换
            {
                string tmp = cur; //定义临时变量，后面的替换不影响cur
                tmp.replace(allpos[j], src[i].size(), dest[i]); //替换子串
                if(!flag[tmp]) 
                {
                    depth[tmp] = depth[cur] + 1;
                    if(depth[tmp] > 10) return false;
                    if(tmp == b) return true;
                    q.push(tmp);
                    flag[tmp] = true;
                }
            } 
        }
    }

    return false;
}

int main()
{
    cin >> a >> b;
    while(cin >> src[cnt] >> dest[cnt]) cnt++;
    
    if(bfs(a)) cout << depth[b];
    else cout << "NO ANSWER!";

    return 0;
}