蒟蒻的双向BFS

tip：小题大做

#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N = 3 * 1e6 + 10,M = 2 * 1e3 + 10,inf = 0x3f3f3f3f;

int st,ed;
int extend(queue<int> &q,unordered_map<int,int> &da,unordered_map<int,int> &db,double d[])
{
    int t = q.front();
    q.pop();
    for(int i=0;i<3;i++)
    {
        if(d[i]==0.5 && t & 1) continue; 
        //special judge：奇数只能由加一或者减一得来，如果是奇数就不能除2
        int n;
        if(i==2) n = t * d[i];
        else n = t + d[i];
        if(da.count(n)) continue; //如果有已出现过的状态叉出去
        if(db.count(n))return da[t] + 1 + db[n]; 
        //如果找到两个状态相遇，返回两个状态记录步数之和+1
        da[n] = da[t] + 1; //记录下一个状态的步数
        q.push(n);
    }
    return -1; //没找到返回-1
}
int two_way_bfs()
{
    double da[3] = {1,-1,2},db[3] = {1,-1,0.5}; //da向前，db向后
    unordered_map<int,int> dista,distb; //记录状态和步数
    dista[st] = 0,distb[ed] = 0; //初始状态步数为0
    queue<int> qa,qb;
    qa.push(st);qb.push(ed);
    while (qa.size()&&qb.size())
    {
        int t;
        // 优先搜索状态少的队列，节约空间
        if(qa.size()<=qb.size()) t = extend(qa,dista,distb,da);
        else t = extend(qb,distb,dista,db);
        if(t!=-1) return t;
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>st>>ed;
    cout<<two_way_bfs();
    return 0;
}
```


```

参考答案：

#include<iostream>
#include<cstring>
#include<queue>
#include<map>

using namespace std;

int n, k;
int res;
map<int, int> mp;

int bfs(int st, int ed)
{
    queue<int> q;
    q.push(st);
    mp[st] = 0;

    while (q.size())
    {
        int a, b, c;
        int t = q.front();
        q.pop();
        if (t == ed) return mp[ed];
        if (!mp[t * 2] && t <= 1e5)
        {
            mp[t * 2] = mp[t] + 1;
            q.push(t * 2);
        }
        if (!mp[t + 1])
        {
            mp[t + 1] = mp[t] + 1;
            q.push(t + 1);
        }
        if (!mp[t - 1])
        {
            mp[t - 1] = mp[t] + 1;
            q.push(t - 1);
        }
    }
    return -1;
}
int main()
{
    cin >> n >> k;

    cout << bfs(n, k) << endl;

    return 0;
}