八数码

八数码，BFS模板题，不做人生不完整

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int maxn = 1000000;

typedef int State[9];

State que[maxn];
State goal;
int dist[maxn];

int vis[362880],fact[9]; 
void init_lookup_table(){
    fact[0]=1;
    for(int i=1;i<9;i++) fact[i]=fact[i-1]*i;
}
//康托展开 
int try_to_insert(int s){
    int code=0;
    for(int i=0;i<9;i++){
        int cnt=0;
        for(int j=i+1;j<9;j++)  if(que[s][i]>que[s][j]) cnt++;
        code+=fact[8-i]*cnt;
    }
    if(vis[code]) return 0;
    return vis[code]=1;
}

const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};
int bfs(){
    init_lookup_table();
    int front = 1, rear = 2;
    while(front!=rear){
        State& s = que[front];
        if(memcmp(s,goal,sizeof(goal))==0) return front;
        int z;
        for(z=0;z<9;z++) if(!s[z]) break;
        int x = z%3, y = z/3;
        for(int i=0;i<4;i++){
            int newx = x+dx[i];
            int newy = y+dy[i];
            int newz = newy*3+newx;
            if(newx>=0 && newx<3 && newy>=0 && newy<3){
                State& t = que[rear];
                memcpy(&t, &s, sizeof(s));
                t[newz] = s[z];
                t[z] = s[newz];
                dist[rear] = dist[front]+1;
                if(try_to_insert(rear)) rear++;
            }
        }
        front++;
    }
    return 0;
}
int main(){
    for(int i=0;i<9;i++)  scanf("%d", &que[1][i]);
    for(int i=0;i<9;i++)  scanf("%d", &goal[i]);
    int ans = bfs();
    if(ans>0) printf("%d\n",dist[ans]);
    else printf("-1\n");
    return 0;
}