当前位置：首页 > 提高组 > 2002年NOIP提高组字串变换解题报告：广度优先搜索与哈希表优化（洛谷P1032）

2002年NOIP提高组字串变换解题报告：广度优先搜索与哈希表优化（洛谷P1032）

4个月前 (07-31)

一、题目解读

“字串变换”问题要求将字符串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;
}