题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

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

using namespace std;

const int N = 6;
string a[N], b[N];
int n;

int extend(queue<string> &q, unordered_map<string, int> &dx, unordered_map<string, int> &dy, string *x, string *y)
{
    auto t = q.front();
    q.pop();

    for (int i = 0; i < t.size(); i ++)
        for (int j = 0; j < n; j ++)
            if (t.substr(i, x[j].size()) == x[j])
            {
                string state = t.substr(0, i) + y[j] + t.substr(i + x[j].size());
                if (dy.count(state)) return dx[t] + 1 + dy[state];//如果dy包含state，说明一定是dx一定不包含，所以下面这步不用判断；
                else if (dx.count(state)) continue;
                q.push(state);
                dx[state] = dx[t] + 1;
            }
    return 11;
}

int bfs(string A, string B)
{
    queue<string> qa, qb;
    unordered_map<string, int> da, db;

    qa.push(A);
    da[A] = 0;
    qb.push(B);
    db[B] = 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;
    }
    return 11;
}
int main()
{
    string A, B;
    cin >> A >> B;
    while(cin >> a[n] >> b[n]) n ++;

    int res = bfs(A, B);
    if (res > 10) puts("NO ANSWER!");
    else cout << res << endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla