1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<iostream>
  7 using namespace std;
  8 struct node
  9 {
 10     int a[4][4],x,y,dep;/*a[4][4]表示的是存着3*3的魔板的状态（存数字）  x,y表示的是空格的位置（存空格）
 11     dep表示的是递归到dep需要多少步 */
 12 }list[400010];
 13 int dx[4]={0,1,0,-1};
 14 int dy[4]={1,0,-1,0};
 15 int d[11];/*康托中使用*/
 16 int head,tail;
 17 bool v[400010];/*v表示这个状态是否来过 */
 18 int kangtuo(node tno)/*康托展开模版*/
 19 /*康托展开，就是把一个方阵换成全排列，如
 20 1 2 3 
 21 4 0 6
 22 7 8 9 换成  1 2 3 4 0 6 7 8 9 ，通过康托展开来全出从小到大的全排列的排序、
 23 通过康托展开看看我们当前这个状态是在全排列中排第几个
 24 公式要运用到阶乘，如果在这里阶乘会很慢，所以在主函数预处理阶乘 
 25 */
 26 {
 27     int b[10]; bool bo[10]; memset(bo,false,sizeof(bo)); int k,len,sum; len=0,sum=0;
 28     for(int i=1;i<=3;i++)
 29     {
 30         for(int j=1;j<=3;j++)
 31         {
 32             len++;
 33             b[len]=tno.a[i][j]+1;
 34         }
 35     }/*把模版中的变化从1开始方便康托展开*/
 36     for(int i=1;i<=9;i++)
 37     {
 38         k=0;
 39         for(int j=1;j<b[i];j++) if(bo[j]==false) k++;
 40         sum=sum+k*d[9-i];/*这里就是康托展开的公式
 41         x=an*(n-1)!+an-1*(n-2)!+...+a1*0!*/
 42         bo[b[i]]=true;
 43     }
 44     return sum+1;/*我们的初始状态是有0的存在*/
 45 }
 46 int main()
 47 {
 48     int tt,k; node tno;
 49     d[0]=1; for(int i=1;i<=9;i++) d[i]=d[i-1]*i;/*预处理阶乘*/
 50     for(int i=1;i<=3;i++)
 51     {
 52         for(int j=1;j<=3;j++)
 53         {
 54             scanf("%d",&list[1].a[i][j]);/*读入初始状态*/
 55             if(list[1].a[i][j]==0)
 56             {
 57                 list[1].x=i;
 58                 list[1].y=j;/*保存空格的坐标*/
 59             }
 60         }
 61     }
 62     list[1].dep=0;/*初始化步数为0*/
 63     for(int i=1;i<=3;i++)
 64         for(int j=1;j<=3;j++)
 65             scanf("%d",&list[0].a[i][j]);/*读入目标状态*/
 66     int ed=kangtuo(list[0]);/*转化目标状态*/
 67     head=tail=1;
 68     memset(v,false,sizeof(v));/*初始化所有状态不存在*/
 69     bool bk=false;/*表示暂时还没有找到合适的可以满足最终状态的状态*/
 70     while(head<=tail)
 71     {
 72         for(int i=0;i<=3;i++)/*四个方向*/
 73         {
 74             tno=list[head];
 75             tno.x=list[head].x+dx[i];
 76             tno.y=list[head].y+dy[i];/*假设空格向上走*/
 77             if(tno.x>=1 && tno.x<=3 && tno.y>=1 && tno.y<=3)/*满足魔板的范围*/
 78             {   
 79                 swap(tno.a[tno.x][tno.y],tno.a[list[head].x][list[head].y]);/*调换空格和魔板的位置*/
 80                 k=kangtuo(tno);/*k代表在全排列中排第几个，通过v来查看有没有这个状态 */
 81                 tno.dep=list[head].dep+1;/*转化了之后步数要增加1，也就是dep增加1*/
 82                 if(v[k]==false)/*k就是他的状态，表示我当前这个状态没有存在过 */
 83                 {
 84                     v[k]=true;/*搜索过，所以更新为存在过，打上标记*/
 85                     tail++;
 86                     list[tail]=tno;/*记录这个状态*/
 87                     if(k==ed)/*满足最终状态*/
 88                     {
 89                         printf("%d\n",tno.dep);/*直接输出步数*/
 90                         bk=true;/*退出*/
 91                         break;
 92                     }
 93                 }
 94             }
 95         }
 96         if(bk==true) break;
 97         head++;
 98     }
 99     return 0;
100 }

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<iostream>
 7 using namespace std;
 8 struct node
 9 {
10     int a[4][4],x,y,dep;
11 }list[400010];
12 int dx[4]={0,1,0,-1};
13 int dy[4]={1,0,-1,0};
14 int d[11];
15 int head,tail;
16 bool v[400010];
17 int kangtuo(node tno)
18 {
19     int b[10]; bool bo[10]; memset(bo,false,sizeof(bo)); int k,len,sum; len=0,sum=0;
20     for(int i=1;i<=3;i++)
21     {
22         for(int j=1;j<=3;j++)
23         {
24             len++;
25             b[len]=tno.a[i][j]+1;
26         }
27     }
28     for(int i=1;i<=9;i++)
29     {
30         k=0;
31         for(int j=1;j<b[i];j++) if(bo[j]==false) k++;
32         sum=sum+k*d[9-i];
33         bo[b[i]]=true;
34     }
35     return sum+1;
36 }
37 int main()
38 {
39     int tt,k; node tno;
40     d[0]=1; for(int i=1;i<=9;i++) d[i]=d[i-1]*i;
41     for(int i=1;i<=3;i++)
42     {
43         for(int j=1;j<=3;j++)
44         {
45             scanf("%d",&list[1].a[i][j]);
46             if(list[1].a[i][j]==0)
47             {
48                 list[1].x=i;
49                 list[1].y=j;
50             }
51         }
52     }
53     list[1].dep=0;
54     for(int i=1;i<=3;i++)
55         for(int j=1;j<=3;j++)
56             scanf("%d",&list[0].a[i][j]);
57     int ed=kangtuo(list[0]);
58     head=tail=1;
59     memset(v,false,sizeof(v));
60     bool bk=false;
61     while(head<=tail)
62     {
63         for(int i=0;i<=3;i++)
64         {
65             tno=list[head];
66             tno.x=list[head].x+dx[i];
67             tno.y=list[head].y+dy[i];
68             if(tno.x>=1 && tno.x<=3 && tno.y>=1 && tno.y<=3)
69             {   
70                 swap(tno.a[tno.x][tno.y],tno.a[list[head].x][list[head].y]);
71                 k=kangtuo(tno);
72                 tno.dep=list[head].dep+1;
73                 if(v[k]==false)
74                 {
75                     v[k]=true;
76                     tail++;
77                     list[tail]=tno;
78                     if(k==ed)
79                     {
80                         printf("%d\n",tno.dep);
81                         bk=true; 
82                         break;
83                     }
84                 }
85             }
86         }
87         if(bk==true) break;
88         head++;
89     }
90     return 0;
91 }