这几天学习了一下双向bfs（好水啊，几天学个这玩意儿），先是找了一道普通的bfs题，写了它的普通版本和双向bfs版本。
这是我写的普通bfs版本（ORZ和别人比起来效率好低啊）
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#define ll long long
#define PI acos(-1)
using namespace std;
int st,ed,vis[10005];
pair<int,int>p;
int bfs()
{
queue<pair<int,int> > q;
q.push(make_pair(st,0));
vis[st] = 1;
while(!q.empty())
{
int te = q.front().first;
int ti = q.front().second;
for(int i = 0;i < 4;i++)
{
int cut = (te / (int)pow(10.0,i) % 10 == 1) ? te + 8 * (int)pow(10.0,i) : te - (int)pow(10.0,i);
int plus = (te / (int)pow(10.0,i) % 10 == 9) ? te - 8 * (int)pow(10.0,i) : te + (int)pow(10.0,i);
if(cut == ed || plus == ed)
return ti + 1;
if(!vis[cut])
{
q.push(make_pair(cut,ti + 1));
vis[cut] = 1;
}
if(!vis[plus])
{
q.push(make_pair(plus,ti + 1));
vis[plus] = 1;
}
for(int i = 0;i < 3;i++)
{
int l = te / (int)pow(10.0,i) % 10;
int r = te / (int)pow(10.0,i + 1) % 10;
int now = te - (l - r) * (int)pow(10.0,i) - (r - l) * (int)pow(10.0,i + 1);
if(now == ed)
{
return ti + 1;
}
if(!vis[now])
{
q.push(make_pair(now,ti + 1));
vis[now] = 1;
}
}
}
q.pop();
}
return -1;
}
int main()
{
int t;
cin >> t;
while(t--)
{
memset(vis,0,sizeof(vis));
cin >> st >> ed;
cout << bfs() << endl;
}
}
娃哈哈，果然双向bfs快了好多啊！！！从450ms提升到了78ms！！！
关键就是在于要把vis设置为一个结构体，下标表示拜访值，flag表示有无拜访，step代表拜访到这个值的时候的step数，然后后sp控制搜索层数就行。
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#define ll long long
#define PI acos(-1)
using namespace std;
int st,ed;
pair<int,int>vis[10005],vis1[10005];
int bfs()
{
queue<pair<int,int> > q,qq;
q.push(make_pair(st,0));
qq.push(make_pair(ed,0));
vis[st].first = 1;
vis1[ed].first = 1;
int sp = -1;
while(!q.empty() && !qq.empty())
{
sp++;
while(q.front().second == sp)
{
int te = q.front().first;
int ti = q.front().second;
for(int i = 0;i < 4;i++)
{
int cut = (te / (int)pow(10.0,i) % 10 == 1) ? te + 8 * (int)pow(10.0,i) : te - (int)pow(10.0,i);
int plus = (te / (int)pow(10.0,i) % 10 == 9) ? te - 8 * (int)pow(10.0,i) : te + (int)pow(10.0,i);
if(vis1[cut] .first)
return vis1[cut].second + ti + 1;
if(vis1[plus].first)
return vis1[plus].second + ti + 1;
if(!vis[cut].first)
{
q.push(make_pair(cut,ti + 1));
vis[cut].first = 1;
vis[cut].second = ti + 1;
}
if(!vis[plus].first)
{
q.push(make_pair(plus,ti + 1));
vis[plus].first = 1;
vis[plus].second = ti + 1;
}
for(int i = 0;i < 3;i++)
{
int l = te / (int)pow(10.0,i) % 10;
int r = te / (int)pow(10.0,i + 1) % 10;
int now = te - (l - r) * (int)pow(10.0,i) - (r - l) * (int)pow(10.0,i + 1);
if(vis1[now].first)
{
return vis1[now].second + ti + 1;
}
if(!vis[now].first)
{
q.push(make_pair(now,ti + 1));
vis[now].first = 1;
vis[now].second = ti + 1;
}
}
}
q.pop();
}
while(qq.front().second == sp)
{
int te = qq.front().first;
int ti = qq.front().second;
for(int i = 0;i < 4;i++)
{
int cut = (te / (int)pow(10.0,i) % 10 == 1) ? te + 8 * (int)pow(10.0,i) : te - (int)pow(10.0,i);
int plus = (te / (int)pow(10.0,i) % 10 == 9) ? te - 8 * (int)pow(10.0,i) : te + (int)pow(10.0,i);
if(vis[cut].first)
return vis[cut].second + ti + 1;
if(vis[plus].first)
return vis[plus].second + ti + 1;
if(!vis1[cut].first)
{
qq.push(make_pair(cut,ti + 1));
vis1[cut].first = 1;
vis1[cut].second = ti + 1;
}
if(!vis1[plus].first)
{
qq.push(make_pair(plus,ti + 1));
vis1[plus].first = 1;
vis1[plus].second = ti + 1;
}
for(int i = 0;i < 3;i++)
{
int l = te / (int)pow(10.0,i) % 10;
int r = te / (int)pow(10.0,i + 1) % 10;
int now = te - (l - r) * (int)pow(10.0,i) - (r - l) * (int)pow(10.0,i + 1);
if(vis[now].first)
{
return vis[now].second + ti + 1;
}
if(!vis1[now].first)
{
qq.push(make_pair(now,ti + 1));
vis1[now].first = 1;
vis1[now].second = ti + 1;
}
}
}
qq.pop();
}
}
return -1;
}
int main()
{
int t;
cin >> t;
while(t--)
{
memset(vis1,0,sizeof(vis1));
memset(vis,0,sizeof(vis));
cin >> st >> ed;
cout << bfs() << endl;
}
}