双向广搜->字符变换(洛谷P1032)

题意：给起始和终止串A和B，以及不超过6个字符串变换规则，求A->B能否在10步以内变换完成。

分析：暴力bfs每次有6条路可以走，时间复杂度是6^10 大概6e8的时间复杂度，会TLE。于是这题是一道经典的双向bfs。 直接开两个队列，两个map，暴力搜1~5步即可。
双向bfs的时间复杂度是2 * (6 ^ 5) = 1e4级别。所以双向bfs在指数级增长的搜索中优势巨大。

'

void solve(){
    string a, b;
    cin >> a >> b;

    vector<pair<string, string>> rules(1);
    //int t = 1;
    while (cin >> rules[0].first >> rules[0].second){
        rules.emplace_back(rules[0]);
       // t ++;if (t > 3) break;
    }
    int rule_size = int(rules.size()) - 1;

    map<string, bool> go;
    map<string, bool> come;
    queue<pair<string, int>> qs, qe;
    qs.emplace(a, 0);
    qe.emplace(b, 0);
    go[a] = true;
    come[b] = true;

    auto bfs = [&]()->int{
        while (!qe.empty() || !qs.empty()){
            int now = qs.front().second;
            if (now >= 5){
                break;
            }
            while (!qs.empty() && qs.front().second == now){
                auto[s, cur] = qs.front();
                qs.pop();
                for (int i = 1; i <= rule_size; ++i){
                    for (int j = 0; j < int(s.size()); ++j){
                        if (s.find(rules[i].first, j) == s.npos){
                            break;
                        }
                        auto tmp_s = s;
                        tmp_s.replace(tmp_s.find(rules[i].first, j), int(rules[i].first.size()), rules[i].second);
                        if (!go.count(tmp_s)){
                            if (come.count(tmp_s)){
                                return (now + 1) * 2 - 1;
                            }
                            qs.emplace(tmp_s, now + 1);
                            go[tmp_s] = true;
                        }
                    }
                }
            }

            now = qe.front().second;
            if (now > 5){
                break;
            }
            while (!qe.empty() && qe.front().second == now){
                auto[s, cur] = qe.front();
                qe.pop();
                for (int i = 1; i <= rule_size; ++i){
                    for (int j = 0; j < int(s.size()); ++j){
                        if (s.find(rules[i].second, j) == s.npos){
                            break;
                        }
                        auto tmp_s = s;
                        tmp_s.replace(tmp_s.find(rules[i].second, j), int(rules[i].second.size()), rules[i].first);
                        if (!come.count(tmp_s)){
                            if (go.count(tmp_s)){
                                return (now + 1) * 2;
                            }
                            come[tmp_s] = true;
                            qe.emplace(tmp_s, now + 1);
                        }
                    }
                }
            }
        }
        return -1;
    };



    int ans = bfs();
    if (ans == -1){
        cout << "NO ANSWER!" << '\n';
    }
    else{
        cout << ans << '\n';
    }

}

'