【搜索】双向广搜

双向广搜

• 双向广搜是单向广搜在时间复杂度上的优化版本，保证在有解情况下效率更高。

---

字串变换

AC代码（y总）：

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

using namespace std;

const int N = 6;

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])
// 这个函数返回qa拓展一层后与qb是否联通：有，返回起点到终点的距离；无，则返回-1或inf表示未联通
{
    int d = da[q.front()];
    while (q.size() && da[q.front()] == d) // 要保证从同一行拓展
    {
        auto t = q.front();
        q.pop();

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

    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] = 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 -1; // 拓展次数已经是10了，再往后找肯定无解了。
    }

    return -1;
}

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

    int t = bfs();
    if (t == -1) puts("NO ANSWER!");
    else cout << t << endl;

    return 0;
}

// * * * 注意：

• 这两个if可以调换顺序。
• 有一个技巧：对于unordered_map<string,int>dis，可以用dis.count(str)来判断是否访问过，不然直接用下标访问可能会出现dis=0的情况（起点），造成误判。因此哈希表记录距离时判断是否访问过要用到这个技巧。

---

走迷宫【双向bfs】

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e3 + 10;
const int inf = 1e9;

int n; 
int a[N][N];
int da[N][N], db[N][N];
typedef pair<int, int> PII;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

int extend(queue<PII> & qa, int da[N][N], int db[N][N])
{
    int d = da[qa.front().first][qa.front().second];
    while(!qa.empty() && d == da[qa.front().first][qa.front().second])
    {
        int x = qa.front().first, y = qa.front().second;
        qa.pop();

        for(int i=0; i<4; i++){
            int xx = x + dx[i], yy = y + dy[i];
            if(xx < 0 || xx >= n || yy < 0 || yy >= n || a[xx][yy] == 1) continue;
            if(db[xx][yy] != -1) return da[x][y] + db[xx][yy] + 1;
            if(da[xx][yy] != -1) continue;

            da[xx][yy] = da[x][y] + 1;
            qa.push({xx, yy});
        }
    }
    return inf;
}

int main()
{
    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) cin >> a[i][j];
    
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) da[i][j] = db[i][j] = -1;
    
    queue<PII>qa, qb;
    qa.push({0, 0});
    qb.push({n - 1, n - 1});
    da[0][0] = db[n - 1][n - 1] = 0;

    while(!qa.empty() && !qb.empty())
    {
        int t;
        if(qa.size() < qb.size()) t = extend(qa, da, db);
        else t = extend(qb, db, da);

        if(t != inf){
            cout << t;
            break;
        }
    }

    cout << endl << endl;

    for(int i=0; i<n; i++, cout << endl)
        for(int j=0; j<n; j++) cout << da[i][j] << " ";
    
    cout << endl;

    for(int i=0; i<n; i++, cout << endl)
        for(int j=0; j<n; j++) cout << db[i][j] << " ";

    system("pause");
    return 0;
}

---

---

---

注意：

• 双向广搜也有跑得慢的时候，例如，起点终点没有路径（不连通），这种情况下单向广搜只搜索起点所在空间，而双向广搜会一并搜索起点和终点所在空间，造成时间上的浪费。因此无解情况下要慎用双向广搜。
• 例如下题。

八数码

TLE代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
const int inf = 1e9;

string st, ed = "12345678x";
vector<int>ne[9] = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4, 6}, {1, 3, 5, 7}, {2, 4, 8}, {3, 7}, {4, 6, 8}, {5, 7}};

int extend(queue<string> & qa, unordered_map<string, int> & da, unordered_map<string, int> & db)
{
    int d = da[qa.front()];
    while(!qa.empty() && d == da[qa.front()])
    {
        string tp = qa.front(); qa.pop();
        int idx = tp.find('x');

        for(auto xx : ne[idx]){
            swap(tp[idx], tp[xx]);
            if(db.count(tp)) return d + 1 + db[tp];
            if(da.count(tp)){
                swap(tp[idx], tp[xx]);
                continue;
            }
            da[tp] = d + 1;
            qa.push(tp);
            swap(tp[idx], tp[xx]);
        }
    }
    return inf;
}

int bfs()
{
    if(st == ed) return 0;

    queue<string>qa, qb;
    unordered_map<string, int>da, db;
    qa.push(st); qb.push(ed);
    da[st] = db[ed] = 0;

    while(!qa.empty() && !qb.empty())
    {
        int t;
        if(qa.size() < qb.size()) t = extend(qa, da, db);
        else t = extend(qb, db, da);

        if(t != inf) return t;
    }

    return -1;
}

int main()
{
    char ch;
    for(int i=0; i<9; i++){
        scanf(" %c", &ch);
        st += ch;
    }

    printf("%d", bfs());

    system("pause");
    return 0;
}