前言：

双向bfs指知道初状态和末状态，从处状态和末状态同时广搜，当一种状态被搜索了两次则说明中间有交织，找到答案。双向BFS一般会比普通BFS快几倍甚至几十倍，当数据较大时。

例题.

八数码：

代码

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int n,g=123804765;
short a[4][4],fx,fy,nx,ny;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1}; 
queue<int> q;
map<int,int> v;
map<int,int> ans;
void solve()
{
    if(n==g)
    {
        printf("0");
        exit(0);
    }
    q.push(n);
    q.push(g);
    ans[n]=0;
    ans[g]=1;
    v[g]=2;
    v[n]=1;
    while(q.size())
    {
        ll now,cur=q.front();
        q.pop();
        now=cur;
        for(int i=3;i>=1;i--)
        for(int j=3;j>=1;j--)
        {
            a[i][j]=now%10,now/=10;
            if(a[i][j]==0) fx=i,fy=j;
        }
        for(int i=0;i<4;i++)
        {
            nx=fx+dx[i];
            ny=fy+dy[i];
            if(nx<1 || nx>3 || ny<1 || ny>3) continue ;
            swap(a[fx][fy],a[nx][ny]);
            now=0;
            for(int p=1;p<=3;p++)
            for(int j=1;j<=3;j++)
            now=now*10+a[p][j];
            if(v[now]==v[cur]) 
            {
                swap(a[fx][fy],a[nx][ny]); 
                continue;
            }
            if(v[now]+v[cur]==3)
            {
              printf("%d",ans[cur]+ans[now]);
                exit(0);
            }
            ans[now]=ans[cur]+1;
            v[now]=v[cur];        
            q.push(now);
            swap(a[fx][fy],a[nx][ny]); 
        }
    }
}
int main()
{
    cin>>n;
    solve();
    return 0;
}

代码应该很好懂。

总结：

如果知道初状态和终状态可以考虑用双向BFS。