题目链接：
http://202.116.77.69/sicily/show_problem.php?pid=1151
（非中大的读者请下载附件）

题目分析：
　　这是一道典型的搜索题，虽然题目没有明确指出求最短指令序列，但关于步数的严格限定使得广搜（BFS）成为了我们的最佳选择。对于广搜，我们首先要解决以下三个问题：

1、队列API
　　广搜的一般操作流程为：
 1）将初始状态压入队列；
 2）测试队列是否非空，若空则成功退出
 3）取出队列首元素；
 4）根据游戏规则枚举所有可能由此状态得到的新状态；
 5）逐个检查各新状态是否进入过队列，若是，跳过；若否，标记为进入过，并压之入队列尾；
 6）跳转到步骤2；
　　由此可见它需要用到队列的压元素、取元素、测试非空操作。队列的实现既可借助于STL list，也可通过自写循环队列实现。笔者基于效率考虑，选择了后者。其实，前者也不过0.05s而已，用时多一倍都不到，也是相当高效的。

2、状态压缩储存
　　题目的输入给出了8个数作为一个状态，但如果我们直接用之进行储存和操作，既浪费时间，也浪费空间，实为不智。所以要把它进行压缩，对于本题，压缩方法有两种：
　　1）用一个8位数来表示，即用12348765来表示状态“1 2 3 4 8 7 6 5”。优点是简明易懂，缺点是比较低效（要通过乘、除、模来取状态位，学过组成原理的同学们都清楚这几个操作是比较费时的）；还有是冗余状态多。本题的有用状态其实只有8!，即约4万个，但采用该法压缩时，状态共有约8765万个。
　　2）考虑到一个状态的每一个位只有1~8这8种选择，所以可以使用3个二进制位进行保存（还记得数字电路的相关内容吗？）即用000表示1，001表示2，010表示3等，如此类推，则“1 2 3 4 8 7 6 5”用二进制数“100,101,110,111,011,010,001,000”（注意是低字在低位，所以1在最后），（补充说明：其实也就相当于八进制数45673210，发现它与原状态的关系了吗？）即十进制的9926280表示。优缺点刚好与前相反。该法的状态共有2^(3*8)=2^24个，即约1670万个（16M），而且比较省时（位操作一般只要一个CPU周期），对于熟练者来说，代码也比较简短。
　　笔者基于时间和空间的考虑选择了后者，具体方法如下：
　　设我用一个int s来保存状态，并把数组a[i]保存到s里边去，可以这样写：s|=(a[i]-1)<<3*i; 其中<<是左移运算符，目的是把a[i]-1的值移动到适当的位中去，然后再通过|=运算写到s中去。举个例子，s原来的值是6，写成二进制是……0000110

3、状态查询
　　回顾广搜操作的第5步，它要求我们能查询一个状态是否进入过队列（在本文中，简称为该状态“是否被扩展过”），由于每生成一个状态都要查询一次，即等于3*8!，约12万次，它是那么的频繁，使得我们必须在O（1）常数时间内返回查询结果，这令我们想起了hash表。
　　对于第一种状态压缩方法，老老实实地写一个hash表是必需的，因为没有足够的空间来保存这么多状态（题目内存限制为32MB，而这种压缩方法的内存需求高达80MB）具体选择可以使用拉链法，既高效，也不易错。
　　而对于第二种状态压缩方法，问题就简单得多了，因为总共只需要16M空间，开一个字符数组char hash[1<<24]足矣！这样不但高效（可能10倍左右吧）而且可以减少达30行的代码！那这个字符数组用来保存什么呢？用来保存生成该状态所用的操作。比如说状态“8 7 6 5 1 2 3 4”（压缩为6850935）是用A操作得到的，则令hash[6850935]='A';//这样的“hash表”是不是很简洁？

　　解决了对于广搜必需解决的问题后，我们再说说一个重要的优化：通常做搜索题时，我们的程序是读入一组数据，就进行一次广搜，但我们注意到，每一次开始搜索时的初始状态都是相同的“1 2 3 4 8 7 6 5”，进而得出结论：每一次搜索后hash表的内容都是相同的！（假如你没有自作聪明做了一些很特别的剪枝的话），这样我们自然会想到：只搜索一次，以后每读入一组数据，就在hash表里查询一下然后输出就可以了~~这一个优化，使总复杂度由O( TestCase * 8! ) 变为 O( 8! + TestCase )，其效率自然成倍地提高。

　　那怎么通过hash表来查询所求状态的操作序列呢？我们观察一下A、B、C三个操作就会发现，它们分别是二循环、四循环、四循环的操作，也就是说对于任意的i，总有A(A(i))=B(B(B(B(i))))=C(C(C(C(i))))=i，于是，若令A(i)=x, B(i)=y, C(i)=z，A(x)=B(B(B(y)))=C(C(C(z)))=i，于是，我们就找到x、y、z的父亲i了！

　　讲到这里，我们已经把各个关键环节全部打通，然后我们的算法自然就呼之欲出了：
　　1）把初始状态1 2 3 4 8 7 6 5”先压缩，再压入队列，开始广搜，结果存入hash表。
　　2）对于每组数据，先压缩，再查询hash表中记录的生成它所使用的操作。
　　3）不断地回溯到其父状态，直到当前状态等于初始状态为止，记录操作序列和所用步数
　　4）输出结果
参考代码：

#include < cstdio > // 用于scanf()、putchar()、printf()等I/O函数
char  hash[ 1 << 24 ]; // hash[i]=得到状态i所用的操作
inline  int  A( int  n) { return  (n & 4095 ) << 12 | n >> 12 ;} // 4095=2^12-1
inline  int  B( int  n) { return  (( 7 << 9 | 7 << 21 ) & n) >> 9   |  ( ~ ( 7 << 9 | 7 << 21 ) & n) << 3 ;}
inline  int  C( int  n) { return  ( 7 | 7 << 9 | 7 << 12 | 7 << 21 ) & n  |  (( 7 << 3 ) & n) << 3   |  (( 7 << 6 ) & n) << 12   |  (( 7 << 18 ) & n) >> 3   |  (( 7 << 15 ) & n) >> 12 ;}
inline  int  zip( int  a[]) { // 用于将8个数压缩为1个小于2^24(约1670万)的整数
    int  s = 0 ;
    for ( int  i = 0 ;i < 8 ; ++ i) s |= (a[i] - 1 ) << ( 3 * i);
    return  s;
}
int  a[] = { 1 , 2 , 3 , 4 , 8 , 7 , 6 , 5 } ; // 初始状态
const   int  QLen = 10000 ; // 队列长度
int  q[QLen],b = 0 ,e = 0 ; // 循环队列及首、尾指针
inline  void  inc( int &  p){ if(++ p ==QLen) p=0;} //用于移动队列首尾指针
int main(){//因为用记事本写的，排版不是很好，请见谅
   int i,j,n,bgn=zip(a);//bgn是初始状态（压缩后）
    hash[bgn]='E';
      q[b]=bgn; inc(b);
      while(b!=e){
         i=q[e]; inc(e);//取队首
         j=A(i);//生成新状态,未访问过则压入hash表和队列
         if(!hash[j]) hash[j]='A', q[b]=j, inc(b);
         j=B(i);
         if(!hash[j]) hash[j]='B', q[b]=j, inc(b);
         j=C(i);
         if(!hash[j]) hash[j]='C', q[b]=j, inc(b);
      }
      char s[100];//s[]用于保存生成的操作序列
      while(scanf("%d",&n),n!=-1){
         for(i=0; i<8; ++i) scanf("%d",&a[i]);
         for(i=zip(a),j=0; i!=bgn; ++j){
            s[j]=hash[i];
            switch(s[j]){//逐步回溯到前一状态
               case 'A': i=A(i);        break;
               case 'B': i=B(B(B(i)));    break;
               case 'C': i=C(C(C(i)));    break;
            }
         }
         if(j>n) printf("-1\n");
         else{
            printf("%d ",j);
            while(j--) putchar(s[j]);
            putchar('\n');
         }
      }
      return 0;
}

写在最后：
　　　　这是我第一次写解题报告，用了整整一个上午的时间，希望大家踊跃支持一下。如果你觉得有所获益，请转告你的朋友，不足之处，请不吝赐教，不明之处，欢迎提问

注：本程序有部分灵感来自辽哥牛牛的同题程序，在此特别鸣谢！