Description

Nine tiles, each with a number from 1 to 9 on it, are packed into a 3 by 3 frame. Your task is to arrange the tiles so that they are ordered as:

1 2 3
4 5 6
7 8 9
       At each step, you can do the following operation to the tiles: Choose 2 by 2 tiles, rotate the tiles in clockwise order. For example:
       1 2 3             4 1 3                           1 2 3             1 2 3
       4 5 6      =>   5 2 6             or           4 5 6      =>   4 8 5
       7 8 9             7 8 9                           7 8 9             7 9 6

       Write a program to find the minimum number of steps.

Input

Input contains multiple test cases.

       Each test case is a description of a configuration of the nine tiles. The description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and from left to right within a row, where the tiles are represented by numbers 1 to 9. For example:
       9 8 7
       6 5 4
       3 2 1
is described by this list:
       9 8 7 6 5 4 3 2 1
Output

Output the minimum number of steps on a single line for each test case.

Sample Input
1 2 3 4 5 6 7 8 9
4 1 3 5 2 6 7 8 9
Sample Output
0
3
解题报告：
　　刚看题目，我马上想到使用宽搜，先把所有情况搜出来，也就是9的阶乘362880种情况。但是由于不能够建立一个九位数的数组来保存这些数据，因此需要使用到康托展开。
　　康托展开的使用范围是对于n个数的排列进行状态的压缩和存储,例如要对9的全排列进行判重.没有必要开一个10的9次幂的数组，因此它有362880中情况。因此其思想就是相当于一个哈希函数。一个排列它所对应的位置就是它排的是第几大。比如321，对应的值就是6，因为前面有个123,132,213,231,312比它小。具体的计算方法见下面代码。C++代码见下面附加代码中的函数cantor（）。
fumction ktzk(s:zrr):longint;
  var i,time,j:longint;
  begin
    for i:= 1 to 12 do
      begin
        time:=0;
        for j:= i+1 to 12 do
          if (s[j]>s[i]) then inc(time);
        inc(ktzk,mi[12-i]*tot);
     end;
end;
　　做完康托展开之后，就要实现四种情况的变换，这个也比较简单，使用四个函数来实现即可，但是写的过程需要特别小心。我这里出了错也是卡了很久。
　　需要注意的是这道题目测试数据较多，刚开始我使用cin，cout结果超时了，排了n久的错，终于想起要把输入输出换为c的。
下面是代码：
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;


const int MAX=362882;
int s[9]={1,10,100,1000,10000,100000,1000000,10000000,100000000};
int jie[9]={0,1,2,6,24,120,720,5040,40320};
int visit[MAX];
int len[MAX];
int four[4];
int lu(int num)
{
    int result;
    result=num%s[4];
    result+=((num/s[5])%10)*s[4];
    result+=num/s[8]*s[5];
    result+=((num/s[6])%10)*s[6];
    result+=((num/s[4])%10)*s[7];
    result+=((num/s[7])%10)*s[8];
    return result;
}

int ru( int num )  
{  
    int result = num/s[5]*s[5];  
    result += num/s[1]%10;  
    result += num/s[4]%10*s[1];  
    result += num/s[2]%10*s[2];  
    result += num%10*s[3];  
    result += num/s[3]%10*s[4];  
  
    return result;  
}  
  
int ld( int num )  
{  
    int result = num/s[6]*s[6] + num%10;  
  
    result += num/s[2]%10*s[1];  
    result += num/s[5]%10*s[2];  
    result += num/s[3]%10*s[3];  
    result += num/s[1]%10*s[4];  
    result += num/s[4]%10*s[5];  
  
    return result;  
}  
  
int rd( int num )  
{  
    int result = num % s[3] + num/s[8]*s[8];  
  
    result += num/s[4]%10*s[3];  
    result += num/s[7]%10*s[4];  
    result += num/s[5]%10*s[5];  
    result += num/s[3]%10*s[6];  
    result += num/s[6]%10*s[7];  
  
    return result;  
}  
int cantor(int key)
{
    int result,temp[9];
    for(int i=8;i>=0;i--)
    {
        temp[i]=key%10;
        key=key/10;
    }
    result=0;

    for(int i=0;i<8;i++)
    {
        int tot=0;
        for(int j=i+1;j<9;j++)
            if(temp[j]<temp[i])
                tot++;
        result+=tot*jie[8-i];
    }
    return result;
}
int key2[4];
int start=123456789;
queue<int>que;
int main()
{

    
    int temp;
    int key1;
    len[0]=0;
    que.push(start);
    visit[0]=1;
    while(!que.empty())
    {
        temp=que.front();
        que.pop();
        key1=cantor(temp);
        four[0]=lu(temp);

        four[1]=ru(temp);

        four[2]=ld(temp);

        four[3]=rd(temp);

        for(int i=0;i<4;i++)
        {
            key2[i]=cantor(four[i]);
            if(!visit[key2[i]])
            {
                visit[key2[i]]=1;
                que.push(four[i]);
                
                len[key2[i]]=len[key1]+1;
            }
        }
    }
    
    int input[9];
    while(scanf("%d",&input[0])!=EOF)
    {
        temp=input[0];
        for(int i=1;i<9;i++)
        {
            scanf("%d",&input[i]);
            temp=input[i]+temp*10;
        }
        printf("%d\n",len[cantor(temp)]);
    }
    return 0;
}

作者: 绿夜 发表于 2011-03-26 00:49 原文链接

Tag sicily 2011. nine digits,宽搜,康托展开,解题报告
推荐.NET配套的通用数据层ORM框架：CYQ.Data 通用数据层框架