魔板

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 1679    Accepted Submission(s): 354

Problem Description

在魔方风靡全球之后不久，Rubik先生发明了它的简化版——魔板。魔板由8个相同大小的方块组成，每一个方块颜色均不相同，可用数字1-8分别表示。任一时刻魔板的状态可用方块的颜色序列表示：从魔板的左上角開始，按顺时针方向依次写下各方块的颜色代号，所得到的数字序列就可以表示此时魔板的状态。比如，序列(1,2,3,4,5,6,7,8)表示魔板状态为：

1 2 3 4

8 7 6 5

对于魔板，可施加三种不同的操作，详细操作方法例如以下：

A: 上下两行互换,如上图可变换为状态87654321

B: 每行同一时候循环右移一格,如上图可变换为41236785

C: 中间4个方块顺时针旋转一格,如上图可变换为17245368

给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。

 

Input

每组測试数据包含两行，分别代表魔板的初态与目态。

 

Output

对每组測试数据输出满足题意的变换步骤。

 

Sample Input

12345678 17245368 12345678 82754631

 

Sample Output

C AC

 

Author

LL

 

Source

 

题目：

做这道题，首先要搞懂 康托展开，具体解释可戳→

我刚開始用BFS做,TLE。。。

后来改用双向BFS，发现WA。。。（我的双向BFS：）

反正终于也没解决，好像是字典序的问题。

看网上其它人预处理一下。（就是打表）

然后这道题能够通过置换来解决：就是从一个状态到还有一个状态能够转换成从起点到某状态）

似懂非懂的感觉，后来看  的博客懂了：

for( i=0;i<8;i++)

pos[s1[i]-'0']=i+1+'0';

for( i=0;i<8;i++)

s2[i]=pos[s2[i]-'0‘]；

k=kangtuo(s2);

上面一段代码的意思是：把起始目标看成了1,2,3,4,5,6,7,8  ;

列如：位置：12345678                12345678

           起初： 63728145       变      12345678

           终点： 86372541       成       51234876

解释一下：初：6在第1个位，那么在终点中找6用1取代，3在第2个位，在终点中找3用2取代，依次类推。

一開始我们就先按 12345678 这种顺序建立了一棵像树一样的，假设直接从初态不进行转变的话，那么我们的结果可能有非常多的走法，有可能是先走A或B都能够到目标，有多条路时,可是先走了B的路径，必需要输出小的也就是从A開始的那条路，那怎么办呢，就能够用转化的思想了，把初始状态变成12345678，这种话，我们一開始就是从这种顺序算出来的！！所以必须先进行转换，在从目标往上找并记下路径，一直找到终于父节点：12345678.

/******************************************************************************        Author:Tree                  **From :http://blog.csdn.net/lttree    ** Title : 魔板                        **Source: hdu 1430                     ** Hint  : 康托展开 BFS                ******************************************************************************/#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;struct Node{    string str,step;};bool vis[40320+1];int  pos[10],fac[] = {1,1,2,6,24,120,720,5040,40320};// ans存从起点到达该点的答案string ans[50000];// 康托展开int kangtuo(string a){    int i,j,t,sum;    sum=0;    for( i=0; i<8 ;++i)    {        t=0;        for(j=i+1;j<8;++j)            if( a[i]>a[j] )                ++t;        sum+=t*fac[8-i-1];    }    return sum+1;}// 按A进行变换void move_A(string &s){    for(int i=0;i<4;++i)        swap(s[i],s[i+4]);}// 按B进行变换string move_B(string s){    string temp=s;    int i;    for(i=0;i<8;++i)    {        if( i==0 || i==4 )  temp[i]=s[i+3];        else    temp[i]=s[i-1];    }    return temp;}// 按C进行变换void move_C(string &s){    swap(s[1],s[2]);    swap(s[5],s[6]);    swap(s[1],s[6]);}void bfs( string s ){    memset(vis,0,sizeof(vis));    queue 
          
            q;    Node pre,lst;    pre.str=s;    pre.step="";    vis[kangtuo(s)]=1;    ans[kangtuo(s)]=pre.step;    q.push( pre );    while( !q.empty() )    {        pre=q.front();        q.pop();        lst=pre;        move_A(lst.str);        if( !vis[kangtuo(lst.str)] )        {            lst.step+="A";            vis[kangtuo(lst.str)]=1;            ans[kangtuo(lst.str)]=lst.step;            q.push(lst);        }        lst.str=move_B(pre.str);        if( !vis[kangtuo(lst.str)] )        {            lst.step=pre.step+"B";            vis[kangtuo(lst.str)]=1;            ans[kangtuo(lst.str)]=lst.step;            q.push(lst);        }        lst=pre;        move_C(lst.str);        if( !vis[kangtuo(lst.str)] )        {            lst.step+="C";            vis[kangtuo(lst.str)]=1;            ans[kangtuo(lst.str)]=lst.step;            q.push(lst);        }    }}int main(){    int i,k;    string s1,s2;    // 预处理，从起点到各点。    bfs("12345678");    while( cin>>s1>>s2 )    {        // 将顺序改过来        // 题目中 12345678         //  事实上是 1234        //         8765        //  我们就依照 12348765来存储        swap(s1[4],s1[7]);        swap(s1[5],s1[6]);        swap(s2[4],s2[7]);        swap(s2[5],s2[6]);        for(i=0;i<8;i++)            pos[s1[i]-'0']=i+1;        for(i=0;i<8;i++)            s2[i]=pos[s2[i]-'0'];/*置换*/        k=kangtuo(s2);        cout<
           
            <