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

#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\n",bfs());

    return 0;

}