【题目来源】
洛谷：[P1032 NOIP 2002 提高组] 字串变换 - 洛谷
【题目描述】
已知有两个字串 A,B 及一组字串变换的规则（至多 6 个规则），形如：
- \(A_1\)\(→\)\(B_1\)。
- \(A_2\)\(→\)\(B_2\)。
规则的含义为：在 \(A\) 中的子串 \(A_1\) 可以变换为 \(B_1\)，\(A_2\) 可以变换为 \(B_2\dots\)。
例如：\(A=abcd\)，\(B＝xyz\)，
变换规则为：
- \(abc→xu\)，\(ud→y\)，\(y→yz\)。
则此时，\(A\) 可以经过一系列的变换变为 \(B\)，其变换的过程为：
- \(abcd→xud→xy→xyz\)。
共进行了 \(3\) 次变换，使得 \(A\) 变换为 \(B\)。
【输入】
第一行有两个字符串 \(A,B\)。
接下来若干行，每行有两个字符串 \(A_i,B_i\)，表示一条变换规则。
【输出】
若在 \(10\) 步（包含 \(10\) 步）以内能将 \(A\) 变换为 \(B\)，则输出最少的变换步数；否则输出 NO ANSWER!。
【输入样例】
abcd xyz
abc xu
ud y
y yz
【输出样例】
3
【解题思路】
【算法标签】
《洛谷 P1032 字串变换》 #字符串# #搜索# #广度优先搜索,BFS# #剪枝# #折半搜索,meet in the middle# #NOIP提高组# #2002#
【代码详解】
#include <bits/stdc++.h>
using namespace std;string a, b; // 初始字符串和目标字符串
string ai[10], bi[10]; // 存储替换规则
int t = 0; // 记录替换规则的数量
int mark; // 记录查找子串的位置// 定义队列节点结构体
struct node
{string s; // 当前字符串int step; // 已进行的替换次数
};int main()
{// 输入初始字符串和目标字符串cin >> a >> b;// 输入替换规则while (cin >> ai[t] >> bi[t]){t++;}// 初始化BFS队列queue<node> q;node tp = {a, 0}; // 初始状态：原始字符串，0次替换q.push(tp);// BFS主循环while (!q.empty()) {node tp = q.front();q.pop();// 如果替换次数已达10次，跳过if (tp.step == 10){continue;}// 尝试所有替换规则for (int i = 0; i < t; i++) {// 查找可以应用当前规则的位置mark = tp.s.find(ai[i]);// 在当前字符串中查找所有匹配位置while (mark != -1) {string ts = tp.s; // 使用临时字符串进行操作// 执行替换操作ts.replace(mark, ai[i].size(), bi[i]);// 检查是否达到目标字符串if (ts == b) {cout << tp.step + 1 << endl;return 0;}// 将新状态加入队列node t = {ts, tp.step + 1};q.push(t);// 继续查找下一个匹配位置mark = tp.s.find(ai[i], mark + 1);}}}// 如果无法在10步内达到目标字符串cout << "NO ANSWER!" << endl;return 0;
}
【运行结果】
abcd xyz
abc xu
ud y
y yz
^Z
3