算法

双向光搜

原因y总说的很明白，我遇到的问题。
要注意的地方。
1.双向光搜一般用在最小步数模型中，因为最小步数一般都是指数级别的，而最短路中一般不会太大，根据题意即可。
2.while 判断条件是两个队列必须都不为空，若为空还未搜到，则说明未联通。
3.substr的用法与熟练度。
4.决策的时候从字符串的每一个位置进行决策，需要二维度空间，每个字符开始的位置进行判断是否满足。
5.两种搜索方式。
1)传统方式，交替搜索，有可能会出现一边搜索空间非常大的可能不采用。
2)优化方式，通过判断两边哪个队列空间，让空间少的一边进行搜索，可保证两边搜索的时候时空比较平均，一般用这种方式比较好。

时间复杂度

参考文献

C++ 代码

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

using namespace std;

const int N = 6;

string a[N], b[N];
int n;

int extend(queue<string>& q, unordered_map<string, int>& da, unordered_map<string, int> &db, string a[], string b[])
{
    auto str = q.front();
    q.pop();

    for(int i = 0; i < str.size(); i ++)
        for(int j = 0; j < n; j ++)
            if(str.substr(i, a[j].size()) == a[j])
            {
                string temp = str.substr(0, i) + b[j] + str.substr(i + a[j].size());
                if(db.count(temp))return da[str] + 1 + db[temp];
                if(da.count(temp))continue;
                da[temp] = da[str] + 1;
                q.push(temp);
            }
    return -1;
}

int bfs(string A, string B)
{
    queue<string> qa, qb;
    unordered_map<string, int> da, db;
    qa.push(A), qb.push(B);
    da[A] = 0, 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 != -1)return t;
    }
    return 11;
}

int main()
{
    string A, B;
    cin >> A >> B;

    while(cin >> a[n] >> b[n])n ++;

    int step = bfs(A, B);

    if(step > 10)puts("NO ANSWER!");
    else cout << step << endl;
    return 0;
}