做淘宝返利网站能挣钱,山东世界500强企业,湖北省建设厅网站怎么打不开,wordpress站点更换域名P1032 [NOIP2002 提高组] 字串变换 - 洛谷 | 计算机科学教育新生态
题目来源
洛谷
题目内容
[NOIP2002 提高组] 字串变换
题目背景
本题不保证存在靠谱的多项式复杂度的做法。测试数据非常的水#xff0c;各种做法都可以通过#xff0c;不代表算法正确。因此本题题目和…P1032 [NOIP2002 提高组] 字串变换 - 洛谷 | 计算机科学教育新生态
题目来源
洛谷
题目内容
[NOIP2002 提高组] 字串变换
题目背景
本题不保证存在靠谱的多项式复杂度的做法。测试数据非常的水各种做法都可以通过不代表算法正确。因此本题题目和数据仅供参考。
本题为搜索题本题不接受 hack 数据。关于此类题目的详细内容
题目描述
已知有两个字串 A , B A,B A,B 及一组字串变换的规则至多 6 6 6 个规则形如 A 1 → B 1 A_1\to B_1 A1→B1。 A 2 → B 2 A_2\to B_2 A2→B2。
规则的含义为在 A A A 中的子串 A 1 A_1 A1 可以变换为 $ B_1 A_2$ 可以变换为 B 2 ⋯ B_2\cdots B2⋯。
例如 A abcd A\texttt{abcd} Aabcd B xyz B\texttt{xyz} Bxyz
变换规则为 abc → xu \texttt{abc}\rightarrow\texttt{xu} abc→xu ud → y \texttt{ud}\rightarrow\texttt{y} ud→y y → yz \texttt{y}\rightarrow\texttt{yz} y→yz。
则此时 A A A 可以经过一系列的变换变为 B B B其变换的过程为 abcd → xud → xy → xyz \texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz} abcd→xud→xy→xyz。
共进行了 3 3 3 次变换使得 A A A 变换为 B B B。
输入格式
第一行有两个字符串 A , B A,B A,B。
接下来若干行每行有两个字符串 A i , B i A_i,B_i Ai,Bi表示一条变换规则。
输出格式
若在 10 10 10 步包含 10 10 10 步以内能将 A A A 变换为 B B B则输出最少的变换步数否则输出 NO ANSWER!。
样例 #1
样例输入 #1
abcd xyz
abc xu
ud y
y yz样例输出 #1
3提示
对于 100 % 100\% 100% 数据保证所有字符串长度的上限为 20 20 20。
【题目来源】
NOIP 2002 提高组第二题
知识点
搜索 字符串题目思路 找最小步数一般用BFS 这是一个字符串转换的问题通过广度优先搜索算法BFS求解将字符串a转换为字符串b的最小步数。整个过程可以分为以下几个步骤 定义全局变量定义字符串a和b原字符串数组origin替换字符串数组translate替换规则数量n转换步数ans和用于记录已访问过字符串的map。实现trans函数该函数在给定字符串str中从位置i开始尝试替换一段子字符串如果能够完成替换则返回替换后的字符串否则返回空字符串。实现bfs函数使用广度优先搜索算法寻找将字符串a转换为字符串b的最小步数。首先将初始状态字符串a步数0入队。然后通过队列不断从头取出字符串判断是否为目标字符串如果是则记录步数并结束搜索。否则标记当前字符串为已访问并尝试对当前字符串的每个位置应用每条替换规则如果替换成功则将新字符串入队并更新步数。最终根据ans的值判断是否有解并输出结果。实现主函数main首先输入原始字符串a和目标字符串b然后输入替换规则直到输入为空。最后调用bfs函数解决问题。 AC代码
//
// Created by Jisam on 2024/7/1.
//
#includebits/stdc.h // 万能头文件包含标准库函数
#define maxn 15
#define PSI pairstring,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为转换步数
mapstring,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() {queuePSI 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;
}
