双向广搜学习笔记

这东西还挺好用的 在已知起始状态和目标状态时用它可以大大减少时间

流程：

起始状态和终点状态入队，并对其打不同标记，假如从起始状态扩展来的点与从终点状态扩展来的点相遇，根据bfs的最优性，可得此时必定时最优答案，直接输出。对于判断哪边来的用个vis数组打打标记就好了

例题 P1379 八数码难题

用个map存状态，然后按照流程走就好了

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <queue>
#define int long long

using namespace std;

map<int,int>vis;
map<int,int>ans;
queue<int>q; 
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int a[4][4];
int endd=123804765,st;

void work() {
    if(st==endd) {
        printf("0");
        return;
    }
    q.push(st); q.push(endd);
    ans[st]=0; ans[endd]=1; //都不等了 说明到最终状态至少1次 
    vis[st]=1; vis[endd]=2;
    while(!q.empty()) {
        int no,x=q.front(),fx,fy,nx,ny;
        q.pop();
        no=x;
        for(int i=3;i>=1;i--)
            for(int j=3;j>=1;j--) {
                a[i][j]=no%10; no/=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]);
            no=0;
            for(int j=1;j<=3;j++)
                for(int k=1;k<=3;k++)
                    no=no*10+a[j][k];
            if(vis[no]==vis[x]) {
                swap(a[fx][fy],a[nx][ny]);
                continue;
            }
            if(vis[no]+vis[x]==3) { //找到必是最优解 
                printf("%lld",ans[x]+ans[no]);
                return;
            }

            ans[no]=ans[x]+1;
            vis[no]=vis[x];
            q.push(no);
            swap(a[fx][fy],a[nx][ny]);
        }
    }
}

signed main() {
    scanf("%lld",&st);
    work();
}

用时286ms 最慢点21ms 可看出双向广搜的确挺快的