2002年NOIP提高组 字串变换 解题报告:广度优先搜索与哈希表优化(洛谷P1032)
一、题目解读
“字串变换”问题要求将字符串A通过一系列规则变换为B,每次变换可替换A中某个子串为指定目标串,输出最少变换步数或“NO ANSWER!”。题目关键在于高效搜索所有可能的变换路径,并避免重复状态。
二、解题思路
采用广度优先搜索(BFS)框架,结合哈希表判重,核心思路如下:
1. 维护队列存储待扩展状态(当前字符串+步数)。
2. 遍历规则集,对每个状态尝试所有规则匹配,生成新串并判重。
3. 剪枝策略:超过10步直接舍弃,避免无效搜索。
4. 利用find()定位子串,replace()替换,减少冗余计算。
三、解题步骤
1. 输入与初始化:读入A、B及规则集,将A入队,标记已访问。
2. BFS主循环:
弹出队首状态,若为B则输出步数并结束。
若步数超限(≥10),跳过当前状态。
遍历规则,定位当前串中所有匹配位置,替换生成新串。
若新串未访问,标记并加入队列,步数+1。
3. 无解处理:队列空时输出“NO ANSWER!”。
四、代码与注释
#include <iostream> #include <queue> #include <unordered_map> #include <string> using namespace std; // 规则结构体(原串→目标串) struct Rule { string from; string to; }; // 状态结构体(当前串+步数) struct State { string str; int step; }; int main() { string A, B; // 输入串A和目标串B cin >> A >> B; vector<Rule> rules; // 存储规则集 string from, to; while (cin >> from >> to) { rules.push_back({from, to}); // 读取规则对 } queue<State> q; // BFS队列 unordered_map<string, bool> visited; // 哈希表判重 q.push({A, 0}); // 初始状态入队 visited[A] = true; // 标记已访问 while (!q.empty()) { State current = q.front(); // 取队首状态 q.pop(); if (current.str == B) { // 到达目标串 cout << current.step << endl; return 0; } if (current.step >= 10) continue; // 剪枝:步数超限跳过 // 尝试所有规则变换 for (const auto& rule : rules) { size_t pos = current.str.find(rule.from); // 查找匹配子串位置 while (pos!= string::npos) { // 可能存在多个匹配 string newStr = current.str; newStr.replace(pos, rule.from.length(), rule.to); // 替换生成新串 if (!visited[newStr]) { // 未访问过则扩展 visited[newStr] = true; q.push({newStr, current.step + 1}); } pos = current.str.find(rule.from, pos + 1); // 继续查找下一个匹配 } } } cout << "NO ANSWER!" << endl; // 无解情况 return 0; }
五、总结
本解法通过BFS保证搜索路径最短,哈希表判重避免重复状态,剪枝策略降低时间复杂度。关键在于灵活运用字符串查找替换API与数据结构优化,体现了算法竞赛中“搜索+剪枝”的经典思想。对于类似字符串变换问题,可借鉴该框架结合具体约束调整实现。
原创内容 转载请注明出处