190. 字串变换(双向BFS，字符串操作，unordered_map)

190. 字串变换 - AcWing题库

已知有两个字串?A,?B?及一组字串变换的规则（至多?66?个规则）:

A1→B1

A2→B2

…

规则的含义为：在?A?中的子串?A1 可以变换为?B1、A2 可以变换为?B2…。

例如：A＝abcd?B＝xyz

变换规则为：

abc?→→?xu?ud?→→?y?y?→→?yz

则此时，A?可以经过一系列的变换变为?B，其变换的过程为：

abcd?→→?xud?→→?xy?→→?xyz

共进行了三次变换，使得?A?变换为?B。

注意，一次变换只能变换一个子串，例如?A＝aa?B＝bb

变换规则为：

a?→→?b

此时，不能将两个?a?在一步中全部转换为?b，而应当分两步完成。

输入格式

输入格式如下：

A?B
A1 B1
A2 B2
…?

第一行是两个给定的字符串?A 和?B。

接下来若干行，每行描述一组字串变换的规则。

所有字符串长度的上限为?20。

输出格式

若在?10?步（包含?10?步）以内能将?A?变换为?B?，则输出最少的变换步数；否则输出?NO ANSWER!。

输入样例：

abcd xyz
abc xu
ud y
y yz

输出样例：

3

解析 ：

双向BFS比单项BFS要快得多，为什么呢：假设每一种状态能扩展出是个状态，那么单项扩展十步就是10^10状态,而如果是双向BFS，其中一段从结果开始，那么两端一共扩展得出的状态是2*10^5
?

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N = 8;
int n;
string A, B;
string a[N], b[N];

int extend(queue<string>& q, unordered_map<string, int>& da, unordered_map<string, int>& db, string a[N], string b[N]) {
    int t = da[q.front()];
    while (q.size() && da[q.front()] == t) {
        auto tt = q.front();
        q.pop();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < tt.size(); j++) {
                if (tt.substr(j, a[i].size()) == a[i]) {
                    string state = tt.substr(0, j) + b[i] + tt.substr(j + a[i].size());
                    if (db.count(state))return da[tt] + db[state] + 1;
                    if (da.count(state))continue;
                    da[state] = da[tt] + 1;
                    q.push(state);
                }
            }
        }
    }
    return 11;
}

int bfs() {
    if (A == B)return 0;
    queue<string>qa, qb;
    unordered_map<string, int>da, db;
    qa.push(A);
    qb.push(B);
    da[A] = 0;
    db[B] = 0;
    int step = 0;
    while (qa.size() && qb.size()) {
        int t;
        if (qa.size() < qb.size()) t=extend(qa, da, db, a, b);
        else t=extend(qb, db, da, b, a);
        if (t <= 10)return t;
        if (++step > 10)return 11;
    }
    return 11;
}

int main() {
    cin >> A >> B;
    while (cin >> a[n] >> b[n])n++;
    int ret = bfs();
    if (ret <= 10)printf("%d\n", ret);
    else printf("NO ANSWER!\n");
    return 0;
}