蓝桥杯， 历届试题 九宫重排 （八数码）

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
typedef struct nn
{
    int loc,c[10],step;
}Node;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int jc[9]={1,1,2,6,24,120,720,5040,40320};
int cantuo(int c[])
{
    int sum=0,k;
    for(int i=0;i<9;i++)
    {
        k=0;
        for(int j=i+1;j<9;j++)
        if(c[j]<c[i]) k++;
        sum+=k*jc[8-i];
    }
    return sum;
}
int find(int c[],int num1,int num2)
{
    if(num1==num2) return 0;
    queue<Node>q;
    Node now,next;
    int x,y,num,tm,f[400000];

    memset(f,0,sizeof(f));
    for(int i=0;i<9;i++)
    {
        if(c[i]==9)
        now.loc=i;
        now.c[i]=c[i];
    }
    now.step=0;
    f[num1]=1;

    q.push(now);
    while(!q.empty())
    {
        now=q.front(); q.pop();
        for(int e=0;e<4;e++)
        {
            x=now.loc/3+dir[e][0];
            y=now.loc%3+dir[e][1];
            if(x>=0&&x<3&&y>=0&&y<3)
            {
                next=now;
                next.step++;
                next.loc=x*3+y;
                tm=next.c[now.loc];
                next.c[now.loc]=next.c[x*3+y];
                next.c[x*3+y]=tm;
                num=cantuo(next.c);
               if(num==num2) return next.step;
                if(!f[num])
                {
                    f[num]=1;
                    q.push(next);
                }
            }
        }
    }
    return -1;
}
int main()
{
    int c[10],tc[10],num1,num2,step;
    char ch[10],tch[10];
    scanf("%s%s",ch,tch);
        for(int i=0;i<9;i++)
        {
            if(ch[i]>=‘1‘&&ch[i]<=‘8‘)
            c[i]=ch[i]-‘0‘;
            else c[i]=9;

            if(tch[i]>=‘1‘&&tch[i]<=‘8‘)
            tc[i]=tch[i]-‘0‘;
            else tc[i]=9;
        }

        num1=cantuo(c);
        num2=cantuo(tc);

        printf("%d\n",find(c,num1,num2));
}