玩具（玩具)

清华OJ——数据结构与算法实验（中国石油大学)

玩具(Toy)

Description

区中心局(Zone Center)上帝最擅长逻辑推理。一天，他谈到了他童年的数码玩具。

玩具像魔方，但不是魔方。具体来说，它不是3 * 3 * 3结构，而是4 * 2结构。

根据玩具的玩法，我们可以通过以下三种方式反复变换3360

A.交换上下线。例如，图(a)的转换结果如图(b)所示。

B.循环右移(ZC从小就知道这意味着什么)。例如，图(b)的转换结果如图(c)所示。

C.中心顺时针旋转。例如，图(c)的转换结果如图(d)所示。

区中心局(Zone Center)上帝在这方面是个天才。他经常有一只手没有擦干鼻子，另一只手已经迅速将玩具在任何状态下恢复到图(a)所示的初始状态。在材料极度匮乏的那一年，ZC神只有一个这样的玩具；如今，材料极其丰富，你在不同的州有许多玩具。现在，请全部恢复。

Input

第一行是正整数，是你拥有的魔方玩具总数。

在以下普通行中的每一行中，包含8个正整数，即1~8的排列，表示玩具的当前状态。

这里，立方体状态的表示规则是，前四个数字从左到右表示立方体的第一行，后四个数字从右到左表示第二行。例如，初始状态表示为"1 2 3 4 5 6 7 8"。

Output

总共普通行，每一行包含一个整数，依次对应需要执行的最小变换次数来还原每个玩具。

特别是，如果玩具不可回收，相应的线路输出-1。

Example

投入

2

1 2 3 4 5 6 7 8

8 6 3 5 4 2 7 1

输出

0

2

Restrictions

60%的

data, N = 1

For 100% of the data,1 = N = 1,000

Time: 1 sec

Memory: 20 MB

Hints

State transition diagram and its search

描述

ZC神最擅长逻辑推理，一日，他给大家讲述起自己儿时的数字玩具。

该玩具酷似魔方，又不是魔方。具体来说，它不是一个3 * 3 * 3的结构，而是4 * 2的结构。

按照该玩具约定的玩法，我们可反复地以如下三种方式对其做变换：

A． 交换上下两行。比如，图(a)经此变换后结果如图(b)所示。

B． 循环右移（ZC神从小就懂得这是什么意思的）。比如，图(b)经此变换后结果如图(c)所示。

C． 中心顺时针旋转。比如，图(c)经此变换后结果如图(d)所示。

ZC神自小就是这方面的天才，他往往是一只手还没揩干鼻涕，另一只手已经迅速地将处于任意状态的玩具复原至如图(a)所示的初始状态。物质极其匮乏的当年，ZC神只有一个这样的玩具；物质极大丰富的今天，你已拥有多个处于不同状态的玩具。现在，就请将它们全部复原吧。

输入

第一行是一个正整数，即你拥有的魔方玩具总数N。

接下来共N行，每行8个正整数，是1~8的排列，表示该玩具的当前状态。

这里，魔方状态的表示规则为：前四个数自左向右给出魔方的第一行，后四个数自右向左给出第二行。比如，初始状态表示为“1 2 3 4 5 6 7 8”。

输出

共N行，各含一个整数，依次对应于复原各玩具所需执行变换的最少次数。

特别地，若某个玩具不可复原，则相应行输出-1。

样例

见英文题面

限制

对于60%的数据，N = 1

对于100%的数据，1 = N = 1,000

时间：1 sec

空间：20MB

提示

状态转换图及其搜索

  1 #includecstdio
  2 #includeiostream
  3 #includecstring
  4 using namespace std;
  5 
  6 int fac[]= {1, 1, 2, 6, 24, 120, 720, 5040, 40320}; //阶乘
  7 
  8 int f(int x)
  9 {
 10     int a[9],k=0;
 11     while(x)
 12     {
 13         a[k++]=x%10;
 14         x/=10;
 15     }
 16 //    for(int i=0;ik;i++)printf("%d",a[i]);
 17 //    printf("\n");
 18     int ans=0,tmp;
 19     for(int i=0; ik; i++)
 20     {
 21         tmp=0;//记录有几个比它小的数
 22         for(int j=i+1; jk; j++)
 23         {
 24             if(a[j]a[i])tmp++;
 25         }
 26         ans+=tmp*fac[k-i-1];
 27     }
 28     return ans;
 29 }
 30 
 31 int dis[45050]={0};
 32 int q[45050],c1=0,c2=0;
 33 int getnum(char a[])
 34 {
 35     int ans=0;
 36     for(int i=0;i8;i++)
 37     {
 38         ans*=10;
 39         ans+=a[i]-'0';
 40     }
 41     return ans;
 42 }
 43 
 44 void bfs()
 45 {
 46     c1=0;
 47     c2=1;
 48     q[0]=12345678;
 49     dis[f(12345678)]=0;
 50     
 51     while(c1!=c2)
 52     {
 53         int now=q[c1++];
 54         
 55         
 56         int next;
 57         char a[10],b[10];
 58         sprintf(a,"%d",now);
 59         now=f(now);
 60         
 61         for(int i=7;i=0;i--)b[i]=a[7-i];
 62     
 63         next=getnum(b);
 64             //printf("aaaa");
 65         int id=f(next);
 66         if(dis[id]==-1)
 67         {
 68             dis[id]=dis[now]+1;
 69             q[c2++]=next;
 70         }
 71         //58763214  a
 72         //87654321  b
 73         b[0]=a[1];
 74         b[1]=a[2];
 75         b[2]=a[3];
 76         b[3]=a[0];
 77         b[4]=a[7];
 78         b[5]=a[4];
 79         b[6]=a[5];
 80         b[7]=a[6];
 81         next=getnum(b);
 82         id=f(next);
 83         if(dis[id]==-1)
 84         {
 85             dis[id]=dis[now]+1;
 86             q[c2++]=next;
 87         }
 88         
 89         //51863724 a
 90         //58763214 b
 91         b[0]=a[0];
 92         b[1]=a[2];
 93         b[2]=a[5];
 94         b[3]=a[3];
 95         b[4]=a[4];
 96         b[5]=a[6];
 97         b[6]=a[1];
 98         b[7]=a[7];
 99         next=getnum(b);
100         id=f(next);
101         if(dis[id]==-1)
102         {
103             dis[id]=dis[now]+1;
104             q[c2++]=next;
105         }
106     }
107 }
108 
109 
110 int main()
111 {
112     memset(dis,-1,sizeof(dis));
113     bfs();
114     
115     int n;
116     scanf("%d",n);
117     while(n--)
118     {
119         int now=0;
120         for(int i=0;i8;i++)
121         {
122             int a;
123             scanf("%d",a);
124             now*=10;
125             now+=a;
126         }
127         
128         printf("%d\n",dis[f(now)]);
129     }    
130     return 0;
131 }