AcWing 190 字串变换 双向BFS

#include <bits/stdc++.h>
using namespace std;
const int N = 100;
string A[N], B[N]; //储存变换方式
int cnt;
string st, ed;

int extend_a(queue<string>& q, unordered_map<string, int>& dis)
{
   
    //对a队列的队首进行拓展
    string t = q.front();
    q.pop();
    int d = dis[t];

    for (int i = 0; i < t.length(); i++) {
     //以字符串的每一个字符作为起点尝试所有变换方式
        for (int j = 0; j < cnt; j++) {
   
            if (t.substr(i, A[j].length()) == A[j]) {
   
                string ns = t.substr(0, i) + B[j] + t.substr(i + A[j].length());
                if (dis.count(ns) == 0) {
   
                    q.push(ns);
                    dis[ns] = dis[t] + 1;
                    d = dis[ns];
                }
            }
        }
    }

    return d;
}

int extend_b(queue<string>& q, unordered_map<string, int>& dis)
{
   
    string t = q.front();
    q.pop();
    int d = dis[t];

    for (int i = 0; i < t.length(); i++) {
     //以字符串的每一个字符作为起点尝试所有变换方式
        for (int j = 0; j < cnt; j++) {
   
            if (t.substr(i, B[j].length()) == B[j]) {
   
                string ns = t.substr(0, i) + A[j] + t.substr(i + B[j].length());
                if (dis.count(ns) == 0) {
   
                    q.push(ns);
                    dis[ns] = dis[t] + 1;
                    d = dis[ns];
                }
            }
        }
    }

    return d;
}

int bfs() 
{
   
    //使用双队列BFS
    unordered_map<string, int> dis_a, dis_b;   //储存到当前状态经历了多少次变换
    queue<string> qa, qb;
    qa.push(st); qb.push(ed);
    dis_a[st] = dis_b[ed] = 0;
    int da = 0, db = 0;          //两端的广搜已经拓展了多少步

    while (!qa.empty() and !qb.empty() and (da + db <= 10) ) {
   
        if (dis_b.count(qa.front())) {
   
            //两端的广搜已经相遇
            return dis_a[qa.front()] + dis_b[qa.front()];
        }
        if (dis_a.count(qb.front())) {
   
            //两端的广搜已经相遇
            return dis_a[qb.front()] + dis_b[qb.front()];
        }
        if (da < db) {
   
            da = extend_a(qa, dis_a);
        }
        else {
   
            db = extend_b(qb, dis_b);
        }
        //两端的拓展方向是相反的
    }

    return 11;
}

int main() 
{
   
#ifndef ONLINE_JUDGE
    freopen("D:/VS CODE/C++/in.txt", "r", stdin);
    freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
    cin >> st >> ed;
    while (cin >> A[cnt] >> B[cnt]) {
   
        ++cnt;
    }

    if (st == ed) {
   
        printf("0");
    }

    int ans = bfs();

    if (ans > 10) {
   
        printf("NO ANSWER!");
    }
    else {
   
        printf("%d", ans);
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}