1 專題說明

本專題用來記錄使用雙向廣搜BFS和A星算法求解的題目。

2 訓練

題目1：190字串變換

考點：從起點開始搜，從終點開始搜，即雙向廣搜。

C++代碼如下，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <string>using namespace std;string start_node, end_node;
vector<pair<string,string>> map_subsrc_subdst;
unordered_map<string, int> dist1; //從起點出發的距離
unordered_map<string, 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并不是唯一的，存在一對多的情況。}queue<string> q1;q1.push(start_node);dist1[start_node] = 0;queue<string> 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：