八數(shù)碼胆筒，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;
}
