BFS优化

双端队列广搜

在普通BFS中，我们默认边权为1，仅当在这个情况下，我们才能够找到最短路，而当边权不为1时，我们就要考虑最短路算法。双端队列广搜就是利用BFS的两端性，来对边权分别为1或0的点进行BFS，使其仍找到最短路。

BFS具有两端性，即在我们进行BFS的过程中，我们的队列只存在两个值，一个是当前走到的距离d，另一个是通过当前距离，然后push到队列里的新的距离d+1，针对这个特点，我们可以用双端队列进行BFS，从而在队尾push d+1的值，在队头push d的值，这样就不影响BFS的顺序了。

175. 电路维修 - AcWing题库

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <deque>

using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
const int maxn = 510;

int n, m;
char g[maxn][maxn];
int dist[maxn][maxn];
bool st[maxn][maxn];

int bfs() {
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    
    dist[0][0] = 0;
    deque<PII> q;
    q.push_back({0, 0});
    
    char cs[] = "\\/\\/";
    int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
    int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
    
    while (q.size()) {
        auto t = q.front();
        q.pop_front();
        
        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = 1;
        
        for (int i = 0; i < 4; i ++ ) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a >= 0 && a <= n && b >= 0 & b <= m) {
                int ca = t.x + ix[i], cb = t.y + iy[i];
                int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);
                
                if (d < dist[a][b]) {
                    dist[a][b] = d;
                    
                    if (g[ca][cb] != cs[i]) q.push_back({a, b}); // 双端队列的特性，对距离为d+1的入队尾，对距离为d的入队头。
                    else q.push_front({a, b});
                }
            }
        }
    }
    return dist[n][m];
}

int main () {
    int tt;
    cin >> tt;
    while (tt -- ) {
        cin >> n >> m;
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
        
        int t = bfs();
        if (t == 0x3f3f3f3f) cout << "NO SOLUTION" << endl;
        else cout << t << endl;
    }
}

双向广搜

双向广搜一般用于最小步数模型中，因为最短路模型中一般搜到的点都不多。而在最小步数模型中，有可能发生TLE或MLE。

双向广搜指的是同时从起点和终点进行BFS，直到他们的状态相等为止，可以理解为首尾双向奔赴。在双向广搜中有一个常用的优化，即每次优先搜索队列状态较小的部分，比如首.size < 尾.size，我们要对首队列进行搜索。

190. 字串变换 - AcWing题库

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

using namespace std;

const int maxn = 6;

int n;
string A, B;
string a[maxn], b[maxn];

int extend(queue<string> &q, unordered_map<string, int> &da, unordered_map<string, int> &db, string a[maxn], string b[maxn]) {
    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;
    }
    return -1;
}

int main () {
    cin >> A >> B;
    while (cin >> a[n] >> b[n]) n ++ ;
    
    int t = bfs();
    if (t == -1) cout << "NO ANSWER!" << endl;
    else cout << t << endl;
    
    return 0;
}