上海网站排名前十,四平英文网站建设,如何创建网页快捷方式,西安网站建设制作目录 1 专题说明2 训练 1 专题说明
本专题用来记录使用双向广搜BFS和A星算法求解的题目。
2 训练
题目1#xff1a;190字串变换
考点#xff1a;从起点开始搜#xff0c;从终点开始搜#xff0c;即双向广搜。
C代码如下#xff0c;
#include iostream
#incl… 目录 1 专题说明2 训练 1 专题说明
本专题用来记录使用双向广搜BFS和A星算法求解的题目。
2 训练
题目1190字串变换
考点从起点开始搜从终点开始搜即双向广搜。
C代码如下
#include iostream
#include cstring
#include algorithm
#include queue
#include unordered_map
#include stringusing namespace std;string start_node, end_node;
vectorpairstring,string map_subsrc_subdst;
unordered_mapstring, int dist1; //从起点出发的距离
unordered_mapstring, int dist2; //从终点出发的距离int main() {cin start_node end_node;string a, b;while (cin a b) {map_subsrc_subdst.emplace_back(a,b); //a-b注意a并不是唯一的存在一对多的情况。}queuestring q1;q1.push(start_node);dist1[start_node] 0;queuestring q2;q2.push(end_node);dist2[end_node] 0;int res -1;while (!q1.empty() !q2.empty()) {//先扩展哪一个扩展数量少的那个if (q1.size() q2.size()) {//扩展q1string t q1.front();q1.pop();if (dist1[t] 10) break;if (dist2.count(t) ! 0) {res dist1[t] dist2[t];break;}//从t可以走到哪里for (auto [subsrc, subdst] : map_subsrc_subdst) {int pos 0;while (t.find(subsrc, pos) ! string::npos) {pos t.find(subsrc, pos);string nt t.substr(0, pos) subdst t.substr(pos subsrc.size());if (dist1.count(nt) 0) { //nt没有被起点扩展到q1.push(nt);dist1[nt] dist1[t] 1;}pos subsrc.size(); //更新pos}}} else {//扩展q2string t q2.front();q2.pop();if (dist2[t] 10) break;if (dist1.count(t) ! 0) {res dist1[t] dist2[t];break;}//从t可以走到哪里for (auto [subdst, subsrc] : map_subsrc_subdst) {int pos 0;while (t.find(subsrc, pos) ! string::npos) {pos t.find(subsrc, pos);string nt t.substr(0, pos) subdst t.substr(pos subsrc.size());if (dist2.count(nt) 0) {//nt没有被终点扩展到q2.push(nt);dist2[nt] dist2[t] 1;}pos subsrc.size(); //更新pos}}}}if (res ! -1) cout res endl;else cout NO ANSWER! endl;return 0;
}题目2
