双向广搜 [NOIP2002 提高组] 字串变换————洛谷p1032

目录

前言

   substr函数

   replace函数

字串变换

   问题描述

   输入

   输出

问题分析

   字符串如何变换

   遍历字符串的所有子串

   剪枝

   qb队列

   注意

代码

---

前言

        在做这题之前，我们先来回顾一下字符串的一些基本操作，这很重要，尤其是本题主要用到substr函数和replace函数

   substr函数

        这是一个取出目标字符串的某个字串的函数，它接收两个参数，返回一个字符串，第一个参数i代表子串开始位置，第二个参数代表该子串的长度，表现为原字符串的索引就是截取了索引为[i,j-i+1]（左闭右闭区间）的字串

#include <iostream>  
#include <string>  
int main() {std::string str = "Hello, World!";// 提取从索引0开始的5个字符  std::string sub1 = str.substr(0, 5); //输出前五个字符std::cout << "Substring 1: " << sub1 << std::endl;  // 输出: Hello  // 提取从索引7开始到末尾的所有字符  std::string sub2 = str.substr(6);// (6:  )  不包括第六个字符std::cout << "Substring 2: " << sub2 << std::endl;  // 输出: World!  // 提取从索引7开始的5个字符（但只会提取到"World"）  std::string sub3 = str.substr(7, 2);  //空格也算字符std::cout << "Substring 3: " << sub3 << std::endl;  // 输出: World  // 尝试提取超出范围的子字符串（会引发异常）  try {std::string sub4 = str.substr(50);  // 50超出了字符串长度  }catch (const std::out_of_range& e) {std::cerr << "Exception: " << e.what() << std::endl;  // 输出: Exception: basic_string::substr: __pos (which is 15) > this->size() (which is 13)  }return 0;
}

   replace函数

        这是一个将目标字符串某一区间的子串替换为另一字符串的函数，它接收三个参数，是自调用函数，无返回值，第一个参数代表子串开始位置，第二个参数代表该子串的长度，表现为原字符串的索引就是截取了索引为[i,j-i+1]（左闭右闭区间）的字串，第三个参数是需替换的字符串，将该字符串替换原字符串索引为[i,j-i+1]（左闭右闭区间）的字串，替换目标和替换对象长度不同也没关系

#include <iostream>  
#include <string>  int main() {std::string str = "Hello, World!";// 假设我们要修改从索引7开始的5个字符（即"World"）  // 我们将把它们替换为"C++"  // 注意："C++"只有3个字符，但我们会替换5个字符，所以后面的两个字符会被删除  str.replace(7, 5, "C++");std::cout << "Modified string: " << str << std::endl;  // 输出: Hello, C++!  // 如果我们只是想修改区间内的某些字符（比如把"World"中的'W'改为'w'），  // 我们可以直接访问字符数组：  if (str.size() > 7 && str[7] == 'W') {str[7] = 'w';  // 修改'W'为'w'  }std::cout << "Modified string (case change): " << str << std::endl;  // 输出: Hello, c++!  return 0;
}

字串变换

原题

   问题描述

        已知有两个字符串A，B，经过一系列变化后由A->B，每次变换可根据相应规则变换A中相应字串，每次变换算一步，问10步之内是否可以完成变换，要求字符串长度上限为20，如果可以，输出最小步数，不行则输出"NO ANSWER!"

   输入

        第一行输入字符串A，B，接下来的几行输入变换规则（不会超过六种）

   输出

        10步之内是否可以完成变换，要求字符串长度上限为20，如果可以，输出最小步数，不行则输出"NO ANSWER!"

问题分析

        本题恒明显是一道bfs题目，遇到bfs题目，首先判断一下它的状态数量多不多，因为bfs中也分双向和单向，每次最多六种状态，10次，那么就是=6000万种，很多，因为这题即使判重，但由于变换规则没有规律性，那么判重减少的状态数也不多，所以还是需要搬出我们的双向广搜

        确定了方法之后，本题还有最关键的两个问题，字符串该如何变换，以及如何或在什么时候遍历字符串的所有子串。

   字符串如何变换

        本题我就不用传统的char数组了，太麻烦了，所以用string变量，那里有一个substr函数，在前言已经说过了，这里就不重复了

   遍历字符串的所有子串

        本来我是想预先对字符串预处理，但是我发现每个状态的字符串都不一样，所以这个遍历操作还是要在入队的时候进行，我承认这很麻烦，但我确实没法子了

这里的i，j就代表我要替换掉区间为[i,j-i+1]（左闭右闭区间）的子串

        接下来就是双向广搜的一些基本操作，如果实在看不懂，强烈建议你去补一补双向广搜基础双向广搜

   剪枝

        本题剪枝不多，唯一一个需要注意的就是，这个双向广搜是双向的，所以每个队列入队的节点的step最多不能超过总共要求步数的一半

   qb队列

        这个qb也就是终点开搜的队列，他的交换规则要反过来，变换成value变成key，因为qb队列相当于模拟起点开搜qa队列的逆过程

   注意

        最后一个需要注意的就是本题很有可能出现给出的变换规则没办法使得A变换到B的情况,在代码中就表现为已经将A的所有变换形态都搜过了，就是没有B，也就是两个队列都空了的情况，此时要输出"NO ANSWER!"

代码

        这里我添加了很多辅助代码，可以放出来试一试，有助于大家理解双向广搜

#include<iostream>  
#include<string>
#include<queue>
#include<map>
#include<vector>
using namespace std;
struct node {string str;int step;node() {}node(string s, int ste) :str(s), step(ste) {}
};struct pair_str {string key;string value;pair_str() {}pair_str(string k, string v) :key(k), value(v) {}
};vector<pair_str>rule;string st, ed;map<string, int>vis;
map<string, int>dis;node now, nxt;
queue<node>qa;
queue<node>qb;void dul_bfs() {qa.push(node(st, 0));qb.push(node(ed, 0));vis[st] = 1;vis[ed] = 2;while (!qa.empty() && !qb.empty()) {if (qa.size() < qb.size()) {now = qa.front();if (now.step >= 5) {cout << "NO ANSWER!" << endl;return;}//cout << "qa出队" << now.str << endl;qa.pop();for (int k = 0; k < rule.size(); k++) {for (int i = 0; i < now.str.size(); i++) {for (int j = i; j < now.str.size(); j++) {string a = now.str.substr(i, j - i + 1);if (rule[k].key == a) {//cout << "qa当前字符" << a << "->" << rule[k].value << endl;//cout << "qa当前修改位置" << i << " " << j << endl;nxt.str = now.str;nxt.str.replace(i, j - i + 1, rule[k].value);//cout << "qa修改后" << nxt.str << endl;if (nxt.str.size() > 20) continue; //剪枝if (vis[nxt.str]==2) {cout << now.step + 1 +dis[nxt.str] << endl;return;}if (!vis[nxt.str]) {vis[nxt.str] = 1;nxt.step = now.step + 1;dis[nxt.str] = nxt.step;//cout << "qa进队" << nxt.str<<"当前步数"<<nxt.step << endl;qa.push(nxt);}}}}}}else {now = qb.front();if (now.step >= 5) {cout << "NO ANSWER!" << endl;return;}//cout << "qb出队" << now.str << endl;qb.pop();for (int k = 0; k < rule.size(); k++) {for (int i = 0; i < now.str.size(); i++) {for (int j = i; j < now.str.size(); j++) {string a = now.str.substr(i, j - i + 1);//注意这里的value和key是反的if (rule[k].value == a) {//cout << "qb当前字符" << a << "->" << rule[k].key << endl;//cout << "qb当前修改位置" << i << " " << j << endl;nxt.str = now.str;nxt.str.replace(i, j - i + 1, rule[k].key);//cout << "qb修改后" << nxt.str << endl;if (nxt.str.size() > 20) continue; //剪枝if (vis[nxt.str] == 1) {cout << now.step + 1 + dis[nxt.str] << endl;return;}if (!vis[nxt.str]) {vis[nxt.str] = 2;nxt.step = now.step + 1;dis[nxt.str] = nxt.step;//cout << "qb进队" << nxt.str<<"当前步数"<<nxt.step << endl;qb.push(nxt);}}}}}}}cout << "NO ANSWER!" << endl; //如果所有队列为空了还没有到答案，那就是这几个转换没有办法将A变到B
}int main() {cin >> st >> ed;string key, value;while(cin >> key >> value){rule.push_back( pair_str(key, value));}dul_bfs();return 0;
}