[Acwing] 190. 字串变换 双向广搜

前言

传送门 : 顾名思义,不过是多了点东西罢了

思路

双向广搜 无非就是 终点和起点 一起搜索罢了(本质上还是 B F S BFS BFS)

这题 起点是 A A A 终点是 B B B

对于搜索 我们还需要记录两个量 :

• 是否枚举过当前状态
• 当前状态已经走了多少步

我们可以使用

  unordered_map da, db

来同时记录 步数 和 是否被遍历

对于当前的 B F S BFS BFS

我们需要对于队头元素进行枚举,从每一个下标枚举所有的修改情况

然后我们做普通的 B F S BFS BFS即可

CODE

#include 
using namespace std;
#define ll long long
#define endl '\n'
#define unmpsi unordered_map
const int N  = 10;
string A,B;
string a[N],b[N];
int n;
int extend(queue& q,unmpsi& da,unmpsi& db,string a[],string b[])
{
    string t  = q.front();
    q.pop();

    int len = t.size();
    for(int i= 0 ;iB;
    while(cin>>a[n]>>b[n]) n++;

    int t = bfs();
    if(t > 10)
    cout