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

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

23小时前

2002年NOIP提高组 字串变换 解题报告:广度优先搜索与哈希表优化(洛谷P1032) NOIP提高组 广度优先搜索 哈希表判重 算法优化 第1张

一、题目解读

字串变换”问题要求将字符串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与数据结构优化,体现了算法竞赛中“搜索+剪枝”的经典思想。对于类似字符串变换问题,可借鉴该框架结合具体约束调整实现。

BFS算法

原创内容 转载请注明出处

分享给朋友:

相关文章

2017年 NOIP 提高组 逛公园(洛谷P3953)题解:代码解析与优化

2017年 NOIP 提高组 逛公园(洛谷P3953)题解:代码解析与优化

一、题目解读    2017年NOIP提高组“逛公园”题目(洛谷P3953)要求在有向图中计算从起点到终点满足特定条件的路径数量。题目难点在于处理路径长度限制与...

2023年GESP五级题「因式分解」洛谷B3871算法解析与代码实现

2023年GESP五级题「因式分解」洛谷B3871算法解析与代码实现

一、题目解读2023年GESP五级题「因式分解」(洛谷B3871)要求将给定的大整数N分解为质因数的乘积形式,并输出每个质因数及其指数。题目考察核心算法为质因数分解,需高效处理大数分解,避免超时。难点...

牛客网288555题解题指南:动态规划求解小红的暑假(附代码解析)

牛客网288555题解题指南:动态规划求解小红的暑假(附代码解析)

一、题目解读牛客网288555题要求解决一个组合数学问题:有三位朋友,每天需邀请其中一位参加聚会,但不能连续两天邀请同一位朋友。给定天数n,求满足条件的不同邀请方案总数。题目考察动态规划、状态转移及组...

【蓝桥杯省赛】2014年A组波动数列题解:动态规划解法与代码解析(C++实现)

【蓝桥杯省赛】2014年A组波动数列题解:动态规划解法与代码解析(C++实现)

一、题目解读“波动数列”是2014年蓝桥杯省赛A组的一道经典题目。题目要求生成一个数列,其前n项的和模n等于给定值s,且每项只能通过加减固定值a、b波动。问题本质是求解满足特定模运算条件的数列组合方案...

2020年NOIP提高组“排水系统”题解(洛谷P7113):拓扑排序与分数分配的图论算法

2020年NOIP提高组“排水系统”题解(洛谷P7113):拓扑排序与分数分配的图论算法

一、题目解读2020年NOIP提高组“排水系统”(洛谷P7113)是一道典型的图论问题,要求解决流量分配问题。题目中给定一个有向图,节点表示排水点,边表示管道连接,每个节点有出度(排水方向)。需计算每...

牛客13279题解:基于广度优先搜索(BFS)计算树高度的算法优化与代码实现

牛客13279题解:基于广度优先搜索(BFS)计算树高度的算法优化与代码实现

一、题目解读牛客13279题要求计算给定树的高度。树由n个节点组成,通过n-1条边连接,形成一棵有根树。题目核心在于高效求解树的高度,即从根节点到最深叶子节点的最长路径长度。需要理解树的结构特点,选择...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。