哈理工oj1049Jigsaw Puzzle解题报告

链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1049
这道题我是用的康托展开做的，优化了判断变化后的数的过程，这道题算是一道数学题吧，应该要算是组合数学里的
View Code
  1 #include<stdio.h>
  2 #include<string.h>
  3 #define N 370000
  4 int used[N];
  5 int g[N];//存储数
  6 int step[N];//每种状态需要的最小步数，为-1则不可达
  7 int fac[10];
  8 int a[9];
  9 int e[10];
 10 void init()
 11 {
 12     int i;
 13     fac[1]=1;
 14     for(i=2;i<10;i++)
 15     fac[i]=i*fac[i-1];
 16     e[0]=100000000;
 17     for(i=1;i<9;i++)
 18     e[i]=e[i-1]/10;
 19 }
 20 int kt(int *a)//康托展开
 21 {
 22     int i,j,k;
 23     int sum=0;
 24     for(i=0;i<9;i++)
 25     {
 26         k=a[i];
 27         for(j=i-1;j>=0;j--)
 28         if(a[j]<a[i])
 29         k--;
 30         sum+=k*fac[8-i];
 31     }
 32     return sum;
 33 }
 34 int getnum(int i,int j,int m)//优化后的程序比原来纯循环要快很多
 35 {
 36     int t1=m/e[i];
 37     int t2=m/e[j];
 38     t1%=10;
 39     t2%=10;
 40     int t=m+(t2-t1)*e[i]+(t1-t2)*e[j];
 41     return t;
 42 }
 43 void bfs(int n)
 44 {
 45     int i,j,k,f,r,p,t;
 46     memset(used,0,sizeof(used));
 47     memset(step,-1,sizeof(step));
 48     f=p=0;
 49     r=1;
 50     g[0]=n;
 51     k=9;
 52     while(k)
 53     {
 54         k--;
 55         a[k]=n%10;
 56         n/=10;
 57     }
 58     t=kt(a);
 59     used[t]=true;
 60     step[t]=0;
 61     while(f<r)//数组模拟队列速度还比较快
 62     {
 63         t=g[f];
 64         k=9;
 65         while(k)
 66         {
 67             k--;
 68             a[k]=t%10;
 69             t/=10;
 70             if(!a[k])
 71             i=k;
 72         }
 73         int temp=kt(a);
 74         if(i>2)
 75         {
 76             a[i]=a[i-3],a[i-3]=0;
 77             int t1=kt(a);
 78             if(!used[t1])
 79             {
 80                 used[t1]=1;
 81                 g[r++]=getnum(i,i-3,g[f]);
 82                 step[t1]=step[temp]+1;
 83             }
 84             a[i-3]=a[i],a[i]=0;
 85         }
 86         if(i<6)
 87         {
 88             a[i]=a[i+3],a[i+3]=0;
 89             int t1=kt(a);
 90             if(!used[t1])
 91             {
 92                 used[t1]=1;
 93                 g[r++]=getnum(i,i+3,g[f]);
 94                 step[t1]=step[temp]+1;
 95             }
 96             a[i+3]=a[i],a[i]=0;
 97         }
 98         if(i%3)
 99         {
100             a[i]=a[i-1],a[i-1]=0;
101             int t1=kt(a);
102             if(!used[t1])
103             {
104                 used[t1]=1;
105                 g[r++]=getnum(i,i-1,g[f]);
106                 step[t1]=step[temp]+1;
107             }
108             a[i-1]=a[i],a[i]=0;
109         }
110         if(i%3<2)
111         {
112             a[i]=a[i+1],a[i+1]=0;
113             int t1=kt(a);
114             if(!used[t1])
115             {
116                 used[t1]=1;
117                 g[r++]=getnum(i,i+1,g[f]);
118                 step[t1]=step[temp]+1;
119             }
120             a[i+1]=a[i],a[i]=0;
121         }
122         f++;
123         //printf("%d %d heih\n",f,r);
124     }
125 }
126 int main()
127 {
128     int t,i;
129     int c=12345678;
130     init();
131     bfs(c);//先把12345678能到达的所有状态都找到存储起来
132     while(scanf("%d",&c)!=EOF)
133     {
134         i=9;
135         while(i)
136         {
137             i--;
138             a[i]=c%10;
139             c/=10;
140         }
141         if(step[kt(a)]!=-1)
142         printf("%d\n",step[kt(a)]);
143         else
144         printf("NO\n");
145     }
146     return 0;
147 }