百度2021秋招笔试相似题目-AcWing 190 变换字符串
双向BFS，降低时间复杂度 get！

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

const int N = 7;

string A,B;
string a[N], b[N];  //存放a->b的变换规则
unordered_map<string,int>qa, qb;   //qa存放节点到起点的距离，qb存放节点到终点的距离
queue<string> q1, q2;
int n = 0;

int extend(queue<string>& v, unordered_map<string,int> &qa, unordered_map<string,int> &qb,
                  string a[], string b[]){
    auto t = v.front();
    v.pop();
    for (int i = 0; i < t.size(); i ++){
        for (int j = 0; j < n; j ++){
            if(t.substr(i, a[j].size()) == a[j]) {
                string newt = t.substr(0,i) + b[j] + t.substr(i + a[j].size());
                if(qb.count(newt)) return qa[t] + 1 + qb[newt];
                if(qa.count(newt)) continue;
                v.push(newt);
                qa[newt] = qa[t] + 1;
            }
        }
    }
    return 11;
}

int bfs(string A, string B){
    int t=0; //最少的步数
    if(A == B) return 0;
    qa[A] = 0, qb[B] = 0; //A到起点的距离为0， B到终点的距离为0
    q1.push(A), q2.push(B);
    while(q1.size() && q2.size()){
        if(q1.size() < q2.size()) t = extend(q1, qa, qb, a, b);
        else t = extend(q2, qb, qa, b, a);
        if(t <= 10) return t;
    }

    return 11;
}

int main(){
    cin >> A >> B;
    while(cin >> a[n] >> b[n]) n++;

    int t = bfs(A,B);
    if(t > 10 ) puts("NO ANSWER!");
    else cout << t;

    return 0;
}