魔板拼图

                                点击打开题目链接

题目大意：给你一个2X4的魔板，问你最少多少步骤能拼成 0 1 2 3
4 5 6 7
0 代表空的地方
如图：

这是最终状态。

Sample Input

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0
Output for the Sample Input

0
1
28

一开始想的是正向来广搜加状态压缩，康拓展开。
用一个int烈性数字表示当前状态，用康拓展开来标记当前状态是否走过，

                                                            康拓展开
             X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! ，其中a[i]为当前未出现的元素中是排在第几个（从0开始）。这就是康托展开。康托展开可用代码实现。

公式编辑
把一个整数X展开成如下形式：
X=a[n](n-1)!+a[n-1](n-2)!+…+a[i]*(i-1)!+…+a[2]*1!+a[1]*0![1]
其中a[i]为当前未出现的元素中是排在第几个（从0开始），并且0<=a[i]

 1 #include <iostream>
 2 #include <stdio.h>
 3 
 4 using namespace std;
 5 
 6 int faction[]={1,1,2,6,24,120,720,5040,40320,362880};
 7 int cantor(int num)
 8 {
 9     int ss=0,i,j,suzi[10];
10     for(i=8;i>0;i--)
11     {
12         suzi[i]=num%10;
13         num/=10;
14     }
15 
16     for(i=1;i<=8;i++)
17     {
18         int couter=0;
19        for(j=i+1;j<=8;j++)
20        {
21            if(suzi[i]>suzi[j]) couter++;
22        }
23        ss=ss+couter*faction[8-i];
24     }
25     return ss+1;
26 }
27 int main()
28 {
29     int x;
30     while(scanf("%d",&x)!=EOF)
31         printf("%d
",cantor(x));
32     return 0;
33 }

代码在这里

正向搜索，广搜答案，TLE

  1 /***************************/
  2 //          正向广搜          /
  3 /***************************/
  4 #include<iostream>
  5 #include<stdio.h>
  6 #include<string.h>
  7 #include<string>
  8 #include<algorithm>
  9 #include<queue>
 10 
 11 using namespace std;
 12 
 13 int vis[40330];
 14 int dir[4]={4,-4,1,-1};
 15 int faction[]={1,1,2,6,24,120,720,5040,40320,362880};
 16 int cantor(int num)
 17 {
 18     int ss=0,i,j,suzi[10];
 19     for(i=8;i>0;i--)
 20     {
 21         suzi[i]=num%10;
 22         num/=10;
 23     }
 24 
 25     for(i=1;i<=8;i++)
 26     {
 27         int couter=0;
 28        for(j=i+1;j<=8;j++)
 29        {
 30            if(suzi[i]>suzi[j]) couter++;
 31        }
 32        ss=ss+couter*faction[8-i];
 33     }
 34     return ss+1;
 35 }
 36 struct node
 37 {
 38     int pos,tai,step;
 39 };
 40 int change(int x,int y,int tai)
 41 {
 42     int i,j,wei;
 43     int su[10],k=0;
 44     while(tai>0)
 45     {
 46         su[k]=tai%10;
 47         tai/=10;
 48         k++;
 49     }
 50     swap(su[8-x],su[8-y]);
 51     tai=0,wei=1;
 52     for(i=1;i<=8;i++)
 53     {
 54         tai=tai+su[i-1]*wei;
 55         wei*=10;
 56     }
 57     return tai;
 58 }
 59 int bfs(int pos,int tai)
 60 {
 61     queue<node>q;
 62     node now,next;
 63     now.pos=pos,now.tai=tai,now.step=0;
 64     vis[cantor(tai)]=true;
 65     q.push(now);
 66     while(!q.empty())
 67     {
 68         now=q.front();
 69         if(now.tai==12345678) return now.step;
 70         q.pop();
 71         for(int i=0;i<4;i++)
 72         {
 73             next.pos=pos=now.pos+dir[i];
 74             if(now.pos==4&&pos==5) continue;
 75             if(now.pos==5&&pos==4) continue;
 76             tai=now.tai;
 77             next.step=now.step+1;
 78             next.tai=tai=change(now.pos,pos,tai);
 79             if(pos>0&&pos<=8&&vis[cantor(tai)]==0)
 80             {
 81                // printf("

%d
%d   %d %d",now.tai,tai,now.pos,pos);
 82                 vis[cantor(tai)]=true;
 83                 q.push(next);
 84             }
 85         }
 86     }
 87     return -1;
 88 }
 89 int main()
 90 {
 91     //freopen("stdin.txt","r",stdin);
 92    // freopen("stdout.txt","w",stdout);
 93     int now;
 94     int maze[10];
 95     while(scanf("%d%d%d%d%d%d%d%d",&maze[0],&maze[1],&maze[2],&maze[3],&maze[4],&maze[5],&maze[6],&maze[7])!=EOF)
 96     {
 97         int i;
 98         memset(vis,0,sizeof(vis));
 99         int tai=0,wei=1;
100         int start;
101         for(i=7;i>=0;i--)
102         {
103             if(maze[i]==1) start=i+1;
104             tai+=(maze[i]+1)*wei;
105             wei*=10;
106         }
107         printf("%d
",bfs(start,tai));
108     }
109 }

View Code

超时了，然后就想了一下，那就打表，反向广搜打表，O(1) 时间复杂度查询

  1 ***************************/
  2 //        反向广搜打表        /
  3 /***************************/
  4 #include<iostream>
  5 #include<stdio.h>
  6 #include<string.h>
  7 #include<string>
  8 #include<algorithm>
  9 #include<queue>
 10 
 11 using namespace std;
 12 const int MM=40325;
 13 bool vis[MM];
 14 int ans[MM];
 15 int dir[4]= {4,-4,1,-1};
 16 int faction[]= {1,1,2,6,24,120,720,5040,40320,362880};
 17 struct node
 18 {
 19     int pos,tai,step;
 20 };
 21 int cantor(int num)
 22 {
 23     int ss=0,i,j,suzi[10];
 24     for(i=8; i>0; i--)
 25     {
 26         suzi[i]=num%10;
 27         num/=10;
 28     }
 29 
 30     for(i=1; i<=8; i++)
 31     {
 32         int couter=0;
 33         for(j=i+1; j<=8; j++)
 34         {
 35             if(suzi[i]>suzi[j]) couter++;
 36         }
 37         ss=ss+couter*faction[8-i];
 38     }
 39     return ss+1;
 40 }
 41 int change(int x,int y,int tai)
 42 {
 43     int i,j,wei;
 44     int su[10],k=0;
 45     while(tai>0)
 46     {
 47         su[k]=tai%10;
 48         tai/=10;
 49         k++;
 50     }
 51     swap(su[8-x],su[8-y]);
 52     tai=0,wei=1;
 53     for(i=1; i<=8; i++)
 54     {
 55         tai=tai+su[i-1]*wei;
 56         wei*=10;
 57     }
 58     return tai;
 59 }
 60 void bfs(int pos,int tai)
 61 {
 62     queue<node>q;
 63     node now,next;
 64     now.pos=pos,now.tai=tai,now.step=0;
 65     vis[cantor(tai)]=true;
 66     q.push(now);
 67     while(!q.empty())
 68     {
 69         now=q.front();
 70         ans[cantor(now.tai)]=now.step;
 71         q.pop();
 72         for(int i=0;i<4;i++)
 73         {
 74             next.pos=pos=now.pos+dir[i];
 75             if(now.pos==4&&pos==5) continue;
 76             if(now.pos==5&&pos==4) continue;
 77             tai=now.tai;
 78             next.step=now.step+1;
 79             next.tai=tai=change(now.pos,pos,tai);
 80             if(pos>0&&pos<=8&&vis[cantor(tai)]==0)
 81             {
 82                 vis[cantor(tai)]=true;
 83                 q.push(next);
 84             }
 85         }
 86     }
 87 }
 88 int main()
 89 {
 90     //freopen("stdin.txt","r",stdin);
 91     // freopen("stdout.txt","w",stdout);
 92     int now;
 93     memset(ans,-1,sizeof(ans));
 94     memset(vis,0,sizeof(vis));
 95     bfs(1,12345678);
 96     int maze[10];
 97     while(scanf("%d%d%d%d%d%d%d%d",&maze[0],&maze[1],&maze[2],&maze[3],&maze[4],&maze[5],&maze[6],&maze[7])!=EOF)
 98     {
 99         int i;
100         int tai=0,wei=1;
101         int start;
102         for(i=7; i>=0; i--)
103         {
104             if(maze[i]==1) start=i+1;
105             tai+=(maze[i]+1)*wei;
106             wei*=10;
107         }
108         printf("%d
",ans[cantor(tai)]);
109     }
110 }