题解：P1032 [NOIP 2002 提高组] 字串变换

lym2022 · 2025-03-26 08:27:35 · 题解

Update 2025.7.18：replace 函数用法中的第一个，替换下标写成了替换下表，感谢评论区大佬指正！

蒟蒻看到这道题的题面就想到了 bfs。

前置知识：

find 函数，在字符串中查找一个子串是否存在，存在返回子串首位的下标，不存在返回 -1，用法 s.find(子串)。

replace 函数，替换字符串中的子串 用法 s.replace(替换下标，要替换的长度，替换的字符串)。

思路：

可以用 map 来标记当前字符串有没有走过，因为蒟蒻不会其他方法，队列的类型可以开 pair，first 开 string 表示当前字符串，second 开 int 表示当前变化过的次数，每次枚举每一个可以变化的方案进行尝试，其他的就是 bfs 模板了，需要注意的是，在变换过程中，每次替换掉子串后需要将替换的位改为别的字符，避免在同一位置已经变换后再次变换。

Code

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

const int N = 20;

int n = 1;

map<string,bool> vis;  //标记数组 

string a[N],b[N],s,t;

void bfs() {
    queue<pair<string,int> > q; 
    q.push({s,0});             //将初始状态进队，步数为0 
    while(!q.empty()) {
        string now = q.front().first;
        string nown = now;                      //存一下未变换时的初始状态 
        int step = q.front().second;
        q.pop();                                //一定要记得删掉！ 
        if(vis[now]) continue;                  //走过了就continue 
        vis[now] = true;
        if(step > 10) continue;                 //超过10步不管走没走到直接continue 
        if(now == t) {                          //走到了，输出当前步数（bfs首解最优） 
            cout << step;
            return;
        }
        for(int i = 1;i<=n;i++) {
            now = nown;                         //每次尝试能否变换为新的字符串前前需要重置当前字符串
            while(true) {
                int p = now.find(a[i]);
                if(p == -1) break;              //找不到就break 
                string str = nown;
                str.replace(p,a[i].size(),b[i]);//替换 
                q.push({str,step+1});           //新状态入队 
                now[p] = ' ';                   //将已经变换的位换成其他字符 
            }
        }
    }
    cout << "NO ANSWER!";                       //s变换不到t，输出无解 
}

int main() {
    cin >> s >> t;
    while(cin >> a[n] >> b[n]) n++;
    n--;
    if(n == 0 && s != t) {             //特判，如果没有可以变换的方案，并且两个字符串不相等，输出无解 
        cout << "NO ANSWER!";
        return 0;
    }
    bfs();
    return 0;
}

这是本蒟蒻的第一篇题解，有什么不足多多指教！