[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} A=abcd， B ＝ xyz B＝\texttt{xyz} B＝xyz，
变换规则为：
- 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 提高组第二题
题目解析
这道题目是一个字符串变换问题，我们需要找出将字符串 A 转换为字符串 B 的最少步骤数，或者判断是否无法在 10 步内完成转换。让我为您分析这道题目并提供解题思路。
题目解析：
- 我们有两个字符串 A 和 B，以及一组变换规则。
- 每个规则允许我们将字符串中的某个子串替换为另一个子串。
- 我们需要找出使用这些规则将 A 转换为 B 的最少步骤数。
- 如果无法在 10 步内完成转换，我们需要输出 “NO ANSWER!”。
解题思路：
这个问题可以使用广度优先搜索（BFS）来解决。以下是具体的步骤：
- 创建一个队列，初始将字符串 A 加入队列。
- 创建一个集合来记录已经访问过的字符串，以避免重复处理。
- 创建一个变量来记录当前的步数，初始为 0。
- 进行 BFS：
a. 当队列不为空且步数小于等于 10 时，执行以下操作：
b. 获取当前队列的大小（当前层的节点数）。
c. 对当前层的每个节点进行处理：- 如果当前字符串等于目标字符串 B，返回当前步数。
- 否则，尝试应用每个变换规则：
- 找到可以应用规则的所有位置。
- 对每个位置，生成新的字符串。
- 如果新字符串没有被访问过，将其加入队列和已访问集合。
d. 当前层处理完毕后，步数加 1。
- 如果 BFS 结束仍未找到目标字符串 B，输出 “NO ANSWER!”。
这种方法的优点是：
- 它保证能找到最少的步骤数（如果存在的话）。
- 它能有效地避免重复状态，提高效率。
- 它能在到达 10 步时及时停止，避免不必要的计算。
实现这个算法时，我们需要注意以下几点：
- 使用 C++ 的 string 类来方便地处理字符串。
- 使用 unordered_set 来快速检查字符串是否被访问过。
- 使用 queue 来实现 BFS。
#include <iostream>
#include <string>
#include <queue>
#include <unordered_set>
#include <vector>
using namespace std;
struct Rule {
string from, to;
};
int bfs(const string& start, const string& target, const vector<Rule>& rules) {
queue<string> q;
unordered_set<string> visited;
q.push(start);
visited.insert(start);
int steps = 0;
while (!q.empty() && steps <= 10) {
int size = q.size();
for (int i = 0; i < size; i++) {
string current = q.front();
q.pop();
if (current == target) {
return steps;
}
for (const Rule& rule : rules) {
size_t pos = 0;
while ((pos = current.find(rule.from, pos)) != string::npos) {
string next = current;
next.replace(pos, rule.from.length(), rule.to);
if (visited.find(next) == visited.end()) {
q.push(next);
visited.insert(next);
}
pos += rule.from.length();
}
}
}
steps++;
}
return -1; // No solution found within 10 steps
}
int main() {
string A, B;
cin >> A >> B;
vector<Rule> rules;
string from, to;
while (cin >> from >> to) {
rules.push_back({from, to});
}
int result = bfs(A, B, rules);
if (result != -1) {
cout << result << endl;
} else {
cout << "NO ANSWER!" << endl;
}
return 0;
}
这个实现使用了上述描述的 BFS 方法。它的主要组成部分是：
Rule结构体用于存储变换规则。bfs函数实现了广度优先搜索算法。- 在
main函数中，我们读取输入并调用bfs函数。
这个解决方案应该能够有效地解决给定的问题。它会找到最少的变换步骤（如果存在的话），或者在无法在 10 步内完成变换时输出 “NO ANSWER!”。
需要注意的是，这个解决方案的时间复杂度可能在最坏情况下相当高，特别是当有很多可能的变换时。然而，考虑到问题的约束（最多 10 步，字符串长度不超过 20），这个解决方案应该能够在合理的时间内处理大多数情况。