8数码，欺我太甚！<bfs+康拓展开>

不多述，直接上代码，至于康拓展开，以前的文章里有

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//阶乘表
int dir[4][2]={1,0,0,1,-1,0,0,-1};//方向
int vis[362881];
int kangst,kanged;
int t1[3][3];
int t2[3][3];
pair<int,int>p;
struct node{
    int maze[3][3];
    pair<int,int>pos;
    int kang;
    int step;
};
int  Kang_open (int t[3][3])
{
    int s[9],num=0,k=0,sum=0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            s[k++]=t[i][j];
    for(int i=0;i<9;i++){
        num=0;
        for(int j=i+1;j<9;j++)
        {
            if(s[i]>s[j])
                num++;
        }
        sum+=num*fac[8-i];
    }
    return sum;
}
int bfs()
{
    node now;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            now.maze[i][j]=t1[i][j];
    now.kang=kangst;
    now.step=0;
    now.pos=p;
    vis[kangst]=1;
    queue<node>que;
    que.push(now);
    while(!que.empty())
    {
        now=que.front();
        que.pop();
        if(now.kang==kanged)
            return now.step;
        node next=now;
        for(int i=0;i<4;i++)
        {
            next=now;
            next.pos.first = now.pos.first+dir[i][0];
            next.pos.second= now.pos.second+dir[i][1];
            if(next.pos.first >=0&&next.pos.first <3&&next.pos.second>=0&&next.pos.second<3)
            {
                next.maze[now.pos.first][now.pos.second]=now.maze[next.pos.first][next.pos.second];
                next.maze[next.pos.first][next.pos.second]=0;
                next.kang=Kang_open(next.maze);
                if(!vis[next.kang])
                {
                    vis[next.kang]=1;
                    next.step++;
                    que.push(next);
                }
            }
        }
    }
    return -1;
}
int main ()
{
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++){
            scanf("%d",&t1[i][j]);
            if(t1[i][j]==0)
                p.first=i,p.second=j;
        }
    kangst=Kang_open(t1);
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            scanf("%d",&t2[i][j]);
    kanged=Kang_open(t2);
    printf("%d
",bfs());
    return 0;
}