P1032-字串变换
题目描述
已知有两个字串A,B及一组字串变换的规则(至多6个规则):
A1 -> B1
A2 -> B2
规则的含义为:在 A中的子串 A1 可以变换为B1,A2可以变换为B2 …。
例如 A="abcd",B="xyz",
变换规则为:
abc
→ xu
,ud
→ y
,y
→ yz
则此时,A可以经过一系列的变换变为B,其变换的过程为:
abcd
→ xud
→ xy
→ xyz
。
共进行了3次变换,使得A变换为B。
输入格式
输入格式如下: A B A1 B1 A2 B2 |-> 变换规则 ... ... / 所有字符串长度的上限为20。
输出格式
输出至屏幕。格式如下:
若在10步(包含10步)以内能将A变换为B,则输出最少的变换步数;否则输出"NO ANSWER!"
输入输出样例
输入 abcd xyz abc xu ud y y yz 输出 3
思路
当看到'输出最少的变换步数',就想到适合用bfs来解决,这题用bfs解决的原理是:先把最初的字符串A串装入队列中,然后依次从队列中取出元素,每次取出元素,都把它可以变换的字符串再装入队列中(比如例题中取出了abcd,就把xud装入队列),当某次装入的字符串正好等于目标字符串B串时,那么它的变换次数就是最少步数,如果队列为空都变换不到B串,则说明A串无法变换为B串。 不过有些需要注意的是: 每个变换规则对每个取出的字符串不一定只用一次,比如字符串为abcabc,变换规则有abc->xu,那么正确的做法是把xuabc和abcxu都装入队列,所以应该用循环来做查找abc而不是只找一次。 需要一个容器记录装入过队列的字符串,当变换的字符串曾经入队过,就不再入队,否则入队并且记录该字符串,这样是为了保证第一次变换出的B串的变换次数就是最少次且不会出现ab变ac,ac又变ab的死循环。由此可见,这个容器需要装入不重复的元素且提供查找元素函数,所以用set容器就很适合。
源码
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<set>
using namespace std;
string keys[7], values[7];
int n; //规则个数
struct Element { //也可以用pair,个人觉得结构体方便些
string str; //当前字符串
int n; //变换次数
};
queue< Element > que;
set<string> seen; //出现过的字符串
string a, b; //初始字符串和目标字符串
int bfs() {
seen.insert(a);
que.push({ a,0 });
while (que.empty() == false) {
Element tmpEle = que.front();
que.pop();
for (int j = 0; j < n; j++) {
int findIdx = -1;
//从第0/上一次匹配位置findIdx 开始查找第j个key
while ((findIdx = tmpEle.str.find(keys[j], findIdx + 1)) != string::npos) {
string str = tmpEle.str;
str.replace(findIdx, keys[j].length(), values[j]); //把字符串中当前查找到的key替换成value
if (seen.find(str) == seen.end()) { //如果没有出现过这个字符串
if (str == b || tmpEle.n + 1 > 11)return tmpEle.n + 1;
que.push({ str,tmpEle.n + 1 });
seen.insert(str);
}
}
}
}
return 11;
}
int main() {
cin >> a >> b;
while (cin >> keys[n] >> values[n])
n++;
int sum = a == b ? 0 : bfs();
if (sum <= 10)cout << sum << endl;
else cout << "NO ANSWER!" << endl;
return 0;
}
相关文章
- [JCIM | 论文简读 ] 有机氟分子亲脂性的快速预测:深度学习提取的极性特征和实验测试
- [IEEE TMI | 论文简读] 基于深度学习的图像生成中噪声和分辨率的线性化分析
- [CVPR 2022 | 论文简读] 基于隐式运动处理的视频伪装物体检测
- [Nature Methods | 论文简读] 人类蛋白质图谱弱监督单细胞分类竞赛分析
- [Nature Methods] 用纳米孔RNA测序直接识别A-I编辑位点
- [Bioinformatics | 论文简读] 用于抗癌药物协同预测的多向关系增强超图表示学习
- [Nature Communications | 论文简读] 利用领域知识进行鲁棒和可泛化深度学习的无CT的PET衰减和散射校正
- [Nature Communications | 论文简读] 通过多视图图协同学习从空间分辨的转录组学数据中阐明肿瘤异质性
- [Nat. Mach. Intell] 用于通过细胞系化合物筛选对个性化临床药物反应鲁棒预测的上下文感知去混杂自编码器
- [Bioinformatics | 论文简读] 通过顺序混合聚类和NMF在上万的细胞中评估单细胞异质性
- [Nat. Mach. Intell. | 论文简读] 对比学习可以快速映射到数百万规模的多模态单细胞图谱
- [IJCAI 2022 | 论文简读] CUP:基于课程学习的隐式事件参数提取提示调优
- [Nature Biotechnology | 论文简读] 使用语言模型和深度学习进行单序列蛋白质结构预测
- [KDD 2022 | 论文简读] HyperAid:用于树拟合和层次聚类的双曲空间去噪
- [JCIM | 论文简读] 用于检测β-内酰胺酶-抑制剂相互作用的可转移多通道模型
- 最佳实践 | 最佳 DevOps 工具链轻松管理软件开发团队的所有工具
- [Nature Methods | 论文简读] SVision:一种解决复杂结构变异的深度学习方法
- [Nature Methods] SpaGCN:整合基因表达、空间位置和组织学,通过图卷积网络识别空间域和空间可变基因
- 基础架构即代码 vs 配置管理 vs 基础架构预配
- [IEEE Trans. Med. Imaging] VQAMix:基于带条件三元组混合的医学图像问答