8 puzzle问题 bfs，输出最少移动次数，输出路径，c++代码

以下是8 puzzle问题的BFS解法的C代码，可以输出最少移动次数和路径：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>

using namespace std;

const int MAXN=3;
const int MAXS=1000000;

int dis[MAXS],fa[MAXS],vis[MAXS],ope[MAXN][MAXN];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
char dir[]="RLDU";

struct node
{
    int s[MAXN][MAXN];
    int x,y;
};

int cantor(int s[][MAXN])
{
    int a[MAXN*MAXN],cnt=0;
    for(int i=0;i<MAXN;i++)
        for(int j=0;j<MAXN;j++)
            a[cnt++]=s[i][j];
    int res=0;
    for(int i=0;i<MAXN*MAXN;i++)
    {
        int num=0;
        for(int j=i+1;j<MAXN*MAXN;j++)
            if(a[i]>a[j])
                num++;
        res+=num*dis[MAXN*MAXN-i-1];
    }
    return res;
}

void decantor(int x)
{
    int a[MAXN*MAXN],cnt=0;
    for(int i=0;i<MAXN*MAXN;i++)
        a[i]=i;
    for(int i=MAXN*MAXN-1;i>=0;i--)
    {
        int t=x/dis[i];
        x%=dis[i];
        ope[cnt/MAXN][cnt%MAXN]=a[t];
        cnt++;
        for(int j=t;j<MAXN*MAXN-1;j++)
            a[j]=a[j+1];
    }
}

void bfs()
{
    queue<node> q;
    node tmp;
    memset(vis,0,sizeof(vis));
    memset(dis,-1,sizeof(dis));
    tmp.x=tmp.y=0;
    memcpy(tmp.s,ope,sizeof(ope));
    int s=cantor(tmp.s);
    dis[s]=0;
    vis[s]=1;
    q.push(tmp);
    while(!q.empty())
    {
        node u=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int nx=u.x+dx[i],ny=u.y+dy[i];
            if(nx<0||nx>=MAXN||ny<0||ny>=MAXN)
                continue;
            node v=u;
            swap(v.s[u.x][u.y],v.s[nx][ny]);
            v.x=nx,v.y=ny;
            int t=cantor(v.s);
            if(!vis[t])
            {
                dis[t]=dis[cantor(u.s)]+1;
                fa[t]=cantor(u.s);
                vis[t]=1;
                q.push(v);
            }
        }
    }
}

int main()
{
    dis[0]=1;
    for(int i=1;i<=MAXN*MAXN;i++)
        dis[i]=dis[i-1]*i;
    for(int i=0;i<MAXN;i++)
        for(int j=0;j<MAXN;j++)
            scanf("%d",&ope[i][j]);
    bfs();
    int ans=dis[MAXN*MAXN-1];
    for(int i=0;i<MAXN;i++)
        for(int j=0;j<MAXN;j++)
            if(ope[i][j])
                ans/=ope[i][j];
    if(dis[cantor(ope)]==-1)
        printf("unsolvable\n");
    else
    {
        printf("%d\n",dis[cantor(ope)]);
        int p=cantor(ope);
        while(p)
        {
            decantor(p);
            for(int i=0;i<MAXN;i++)
            {
                for(int j=0;j<MAXN;j++)
                {
                    printf("%d ",ope[i][j]);
                }
                printf("\n");
            }
            printf("\n");
            p=fa[p];
        }
    }
    return 0;
}

需要注意的是，输入的初始状态需要保证是可解的，如果不可解则输出"unsolvable"。