NOIP 2002 提高组洛谷P1032"字串变换"的BFS解法与优化策略

9个月前 (06-07)比赛题解288

一、问题描述

给定初始字符串A和目标字符串B，以及若干变换规则（将特定子串替换为另一子串）。要求通过不超过10步变换，将A转换为B，求最少变换步数。若无法在10步内完成，输出"NO ANSWER!"。

二、解题思路

广度优先搜索(BFS)：适用于状态最少步数探索
字符串处理：使用C++ string的find和replace方法
去重优化：记录已访问状态避免重复计算

三、C++代码实现

#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;
    cin >> A >> B;
    
    vector<Rule> rules;
    string from, to;
    while (cin >> from >> to) {
        rules.push_back({from, to});
    }
    
    queue<State> q;
    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;
}