luogu1376八数码|题解

本来是想拿这个题来练习双向bfs的 结果一开始连朴素写法都写不出来
终于坎坷地打完代码 所以来发个题解
双向bfs+map判重
如果不加双向会t一个点 加完就能ac
代码比较丑 大家将就看看吧

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <queue>
#include <map>//个人惯用的头文件
using namespace std;
struct xxx{
    string str;
    short i;
};//i表示0在串中的位置
bool check(int i,int d){//d是0移动的方向 详见下方dic数组
    if((i + d > 8)||(i + d < 0)) return 0;
    if((i % 3 == 0)&&(d == -1)) return 0;
    if((i % 3 == 2)&&(d == 1)) return 0;
    return 1;
}//分别判断0的位置进行变化后是否合法 
int dic[4] = {1,-1,3,-3};//0变化的四种方向
map <string,int> m1,m2;
queue <xxx> q1,q2;//两个队列和map别用于两个bfs方向
xxx st,ed;//起始和终止状态存储
int c,c1 = 1,c2 = 1,cc = 0;//分别表示计数器、当前层级正方向的状态总数、当前层级负方向的状态总数、当前层级
int bfs(){
    while (!q1.empty()){
        ++ cc;//更新当前层级
        xxx lx,x;//lx用于取出队首 x用于变化操作

        c = c1;
        c1 = 0;
        for (int i = 1;i <= c;++ i){//遍历当前层级正方向的所有状态
            lx = q1.front();q1.pop();//取队头

            for (int z = 0;z < 4;++ z){//四种移动方向
                x = lx;//重置x
                int d = dic[z];
                if(!check(x.i,d)) continue;//判断移动是否合法
                swap(x.str[x.i],x.str[x.i + d]);
                x.i += d;//更新x的状态

                if (m1[x.str]) continue;
                q1.push(x);m1[x.str] = 1;++ c1;//判断是否重复 不重复时将新状态存入队 且更新c1

                if (m2[x.str]) return cc * 2 - 1;//判断是否在上一层的反方向上出现过该状态 有则返回（当前层级+上一层层级）（即cc*2 - 1）
            }
        }
        //-------------------------------以下是反方向的处理 与正方向相同
        c = c2;
        c2 = 0;
        for (int i = 1;i <= c;++ i){
            lx = q2.front();q2.pop();

            for (int z = 0;z < 4;++ z){
                x = lx;
                int d = dic[z];
                if(!check(x.i,d)) continue;
                swap(x.str[x.i],x.str[x.i + d]);
                x.i += d;

                if (m2[x.str]) continue;
                q2.push(x);m2[x.str] = 1;++ c2;

                if (m1[x.str]) return cc * 2;//这里应为判断同层级的正方向是否出现过该状态 有则返回（当前层级+当前层级）
            }
        }
    }
}
int main (){
    cin >> st.str;
    for (int i = 0;i < 9;++ i){
            if(st.str[i] == '0')    st.i = i;
    }//读入 处理0的位置
    ed = (xxx){"123804765",4};
    q1.push(st);m1[st.str] = 1;
    q2.push(ed);m2[st.str] = 1;//初始化
    if(st == ed){
        printf("0");
        return 0;
    }//特判是否只有一个状态
    printf("%d",bfs());//进入bfs
    return 0;
}