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

问题描述　　如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

　　我们把第一个图的局面记为：12345678.
　　把第二个图的局面记为：123.46758
　　显然是按从上到下，从左到右的顺序记录数字，空格记为句点。

　　本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。输入格式　　输入第一行包含九宫的初态，第二行包含九宫的终态。输出格式　　输出最少的步数，如果不存在方案，则输出-1。样例输入 12345678.
123.46758 样例输出 3 样例输入 13524678.
46758123. 样例输出 22

#include
  
   
#include
   
     #include
    
      #include
     
       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]
      
       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)); }

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