2522: 【普及+/提高】【P1032】字串变换
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
已知有两个字串 及一组字串变换的规则（至多 个规则），形如：
- 。
- 。
规则的含义为：在 中的子串 可以变换为 ， 可以变换为 。
例如：，，
变换规则为：
- ，，。
则此时， 可以经过一系列的变换变为 ，其变换的过程为：
- 。
共进行了 次变换，使得 变换为 。
输入
第一行有两个字符串 。
接下来若干行，每行有两个字符串 ，表示一条变换规则。
输出
若在 步（包含 步）以内能将 变换为 ，则输出最少的变换步数；否则输出
NO ANSWER!。样例输入 复制
abcd xyz
abc xu
ud y
y yz样例输出 复制
3提示
对于 数据，保证所有字符串长度的上限为 。
#include<bits/stdc++.h>
using namespace std;
struct point {
string s;
int step;
};
int main(){
string a,b,ai[10],bi[10];
int t = 0;
cin >> a >> b;
while (cin >> ai[t] >> bi[t]) t++;
queue <point> q;
q.push({a,0});
while(!q.empty()) {
point p=q.front();
q.pop();
if (p.step == 10 ) continue;
for (int i = 0; i < t; i++) {
int mark=p.s.find(ai[i]);
while (mark != -1) {
string ts=p.s;
ts.replace(mark,ai[i].size(),bi[i]);
if (ts == b) {
cout << p.step + 1;
return 0;
}
q.push(point{ts,p.step + 1});
mark = p.s.find(ai[i],mark + 1);
}
}
}
cout << "NO ANSWER!";
return 0;
}