BFS(双向广搜)

Acwing 190.字串变换

Acwing 算法提高课 BFS(双向广搜)

双向广搜是指同时从起点和终点两个方向开始扩展，从而减少总共状态次数的BFS*优化方法

适用：主要是最少步数模型，因为FloodFill和最短路的总共状态数都相对较少，所以优化作用较弱

$$优化表现：在本题中，每一个字符串扩展出约6种状态$$ $$单向广搜的最后一层(10,题目规定)的状态个数 n_{单} = 6 ^ {10}$$ $$若使用双向广搜，两边边的最大状态数和为 n_{双} = 2 \times 6 ^ {5}$$ $$不难计算,优化了近4000倍$$

一般框架:
 分为两个函数：I. BFS II. Extend(扩展)
     I .BFS
         (i  创建两个队列(首和尾)以及对应的距离(首和尾)
         (ii while循环扩展 注意这里的条件是qa.size() && qb.size() 因为其中有一者扩展完说明不连通
             while内部是判断a和b种元素的多少,选取元素少的那一者进行扩展(小优化)
                 Extend(...)
     II .Extend()
         (i  传参 : 对应的队列(现在在扩展哪一边),两个队列的距离(用于判断是否有搜到和更新),扩展规则(本题中是字符串变换规则)   
         (ii 枚举同层状态和下一状态 ：得到state(下一状态)后,在两个距离中判断 若qa(现在在枚举的队列)中有这个状态了就不重复更新
                                                                    若qb(对面的队列)中有这个状态则说明搜到了则直接返回距离(da + 1 + db)
         (iii若到这，说明没搜到，可返回 -1(本题是11,题目要求<=10所以与-1等效)

参考文献

https://www.acwing.com/activity/content/code/content/132167/

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

using namespace std;

const int N = 10;

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

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

int bfs(){
    unordered_map<string, int> da, db;
    queue<string> qa, qb;
    qa.push(st), qb.push(ed);
    da[st] = 0, db[ed] = 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(){
    
    cin >> st >> ed;
    while(cin >> a[n] >> b[n]) n ++;
    
    if(st == ed){
        puts("0");
        return 0;
    }
    int t = bfs();
    
    if(t > 10) puts("NO ANSWER!");
    else printf("%d\n", t);
    
    return 0;
}