P1032 [NOIP2002 提高组] 字串变换 - 洛谷 | 计算机科学教育新生态

题目来源

洛谷

题目内容

[NOIP2002 提高组] 字串变换

题目背景

本题不保证存在靠谱的多项式复杂度的做法。测试数据非常的水，各种做法都可以通过，不代表算法正确。因此本题题目和数据仅供参考。

本题为搜索题，本题不接受 hack 数据。关于此类题目的详细内容

题目描述

已知有两个字串 $A,B$ 及一组字串变换的规则（至多 $6$ 个规则），形如：

• $A_1\to B_1$。
• $A_2\to B_2$。

规则的含义为：在 $A$ 中的子串 $A_1$ 可以变换为 $ B_1$，$A_2$ 可以变换为 $B_2\cdots$。

例如：$A=\text{abcd}$，$B＝\text{xyz}$，

变换规则为：

• $\text{abc}\to \text{xu}$，$\text{ud}\to \text{y}$，$\text{y}\to \text{yz}$。

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

• $\text{abcd}\to \text{xud}\to \text{xy}\to \text{xyz}$。

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

输入格式

第一行有两个字符串 $A,B$。

接下来若干行，每行有两个字符串 $A_i,B_i$，表示一条变换规则。

输出格式

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

样例 #1

样例输入 #1

abcd xyz
abc xu
ud y
y yz

样例输出 #1

3

提示

对于 $100\%$ 数据，保证所有字符串长度的上限为 $20$。

【题目来源】

NOIP 2002 提高组第二题

知识点

搜索 字符串

题目思路

找最小步数一般用BFS

这是一个字符串转换的问题，通过广度优先搜索算法（BFS）求解将字符串a转换为字符串b的最小步数。整个过程可以分为以下几个步骤：

1. 定义全局变量：定义字符串a和b，原字符串数组origin，替换字符串数组translate，替换规则数量n，转换步数ans，和用于记录已访问过字符串的map。
2. 实现trans函数：该函数在给定字符串str中，从位置i开始尝试替换一段子字符串，如果能够完成替换，则返回替换后的字符串，否则返回空字符串。
3. 实现bfs函数：使用广度优先搜索算法，寻找将字符串a转换为字符串b的最小步数。首先将初始状态（字符串a，步数0）入队。然后通过队列不断从头取出字符串，判断是否为目标字符串，如果是则记录步数并结束搜索。否则，标记当前字符串为已访问，并尝试对当前字符串的每个位置应用每条替换规则，如果替换成功，则将新字符串入队并更新步数。最终根据ans的值，判断是否有解并输出结果。
4. 实现主函数main：首先输入原始字符串a和目标字符串b，然后输入替换规则，直到输入为空。最后调用bfs函数解决问题。

AC代码

//
// Created by Jisam on 2024/7/1.
//
#include<bits/stdc++.h>		// 万能头文件，包含标准库函数
#define maxn 15
#define PSI pair<string,int>
#define x first
#define y second
using namespace std;

// 全局变量声明
string a, b; // 原始字符串a和目标字符串b
string origin[maxn]; // 原字符串数组
string translate[maxn]; // 替换字符串数组
int n, ans; // n为替换规则数量，ans为转换步数
map<string,int> ma; // 用于记录已访问过的字符串

/**
 * @brief 尝试在字符串str中，从位置i开始替换一段子字符串
 *
 * @param str 待处理的字符串
 * @param i 替换开始的位置
 * @param j 替换所使用的规则索引
 * @return string 如果可以进行替换，则返回替换后的字符串，否则返回空字符串
 */
string trans(const string &str, int i, int j) {
    string res = "";
    // 检查是否可以完成替换
    if(i + origin[j].length() > str.length()) {
        return res;
    }
    for(int k = 0; k < origin[j].length(); k ++) {
        if(str[i + k] != origin[j][k]) {
            return res;
        }
    }
    // 实现替换操作
    res = str;
    res = res.replace(i, origin[j].size(), translate[j]);
//    res = str.substr(0,i)
//          + translate[j]
//          + str.substr(i + origin[j].length());
    return res;
}

/**
 * @brief 使用广度优先搜索算法，寻找将字符串a转换为b的最小步数
 */
void bfs() {
    queue<PSI> q;
    q.push({a, 0}); // 将初始状态（字符串a，步数0）入队

    while(!q.empty()) {
        PSI f = q.front();
        q.pop();

        // 如果当前字符串已记录过，则跳过
        if(ma.count(f.x) == 1) {
            continue;
        }

        // 如果找到目标字符串，则记录步数并结束搜索
        if(f.x == b) {
            ans = f.y;
            break;
        }
        ma[f.x] = 1; // 标记当前字符串为已访问

        // 尝试对当前字符串的每个位置应用每条替换规则
        for(int i = 0; i < f.x.length(); i ++) {
            for(int j = 0; j < n; j ++) {
                string t = trans(f.x, i, j);
                // 如果替换成功，则将新字符串入队
                if(!t.empty()) {
                    q.push({t, f.y + 1});
                }
            }
        }
    }

    // 根据ans的值，判断是否有解并输出结果
    if(ans > 10 || ans == 0) {
        cout << "NO ANSWER!" << endl;
    } else {
        cout << ans << endl;
    }
}

int main() {
    cin >> a >> b; // 输入原始字符串a和目标字符串b

    // 输入替换规则，直到输入为空
    while(cin >> origin[n] >> translate[n]) {
        n ++;
    }

    bfs(); // 调用广度优先搜索算法

    return 0;
}