题意：把由 8 个立方体和一个空格组成的方阵通过滚动立方体到相邻的空格使上表面呈现所需的图案，滚动步数 30 步以上则输出-1。(65MB,5s)

需要注意的是：1. 所有立方体着色方式相同，立方体相对面颜色相同。2. 一开始的所有立方体按相同的方式摆放，白色朝上蓝色朝右，空格可以随意放置。3. 结束状态有 256 种，因为图案相同的状态有 2⁸ 种 (每个立方体绕法线旋转后图案相同)。

思路：由于这道题类似于 8 数码问题，所以可以使用广搜。注意到空间限制比较苛刻，所以对空间的优化成为主要矛盾。

搜索时判重很重要。

1. 网上主流的判重方法是：依此存储每个方块的摆放方式（6 进制）, 状态数=15116544, 用 int 型数组可以保存。这已经是最优的方案了，每一个 hash 值对应一个状态。然而，其唯一的缺点是代码冗长。2. 如果用一个 7 进制数来保存状态的话，状态数=40353607，用 char 型数组保存，空间占用其实比上一种方案还要小（当然上一种方案用 char 来保存更小）。这样获得 hash 值的函数只需要 5 行，更新只需要 2 行，效率也更高。所以本程序采用的是第二种方案。

接下来讨论如何搜索。

用一个手写队列保存扩展出的每一种状态，用循环队列充分利用空间。考虑到正向搜索的初始状态数比较少，逆向搜索的初始状态数比较多，并且搜索层数只需要在 30 层以下，所以可以先正向搜索 20 层，逆向搜索 10 层使得总状态数和最小从而搜索时间最短。为了更充分的利用空间，hash 数组只开一个，初始化为-1;

第一次搜索时 hashmap 用来保存步数;

第二次搜索时 因为步数可以保存在队列里，所以 hashmap 只起到判重的作用。如果第二次搜索时某状态与第一次的结果重合（即hashmap[x]>=0）, 用 此时的步数+hashmap[x] 更新最小步数。如果当前的步数大于等于最小步数，则退出搜索。

至此，我们获得了一个空间需要 47MB, 时间 1.5s 的算法, 并且行数只有 130 行。

注释：(程序中用来表示各种状态的数字)

立方体的颜色：White=1;Blue=2;Red=3

立方体的状态：

状态:————-1: 2: 3: 4: 5: 6:

俯视图 (上, 右)–13 12 23 21 32 31

俯视图 (前)——2 3 1 3 1 2

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

#define MD 41000000
#define MX 200001
#define FM 20
#define BM 10

typedef struct my_st
{
    char x[9];
    int blank,hs,step;
} state;

char hsmap[MD],nowwork[9],xnxt[7]={0,6,4,5,2,3,1},ynxt[7]={0,3,5,1,6,2,4};  //分别时 hash 数组，输入时的临时数组，横向滚动和纵向滚动的转移序列
int seven[9]= {1,7,49,343,2401,16807,117649,823543,5764801};                //保存 7 的幂
int vec[5][3]= {{0,0,0},{0,0,1},{0,0,-1},{0,1,0},{0,-1,0}};                 //滚动方向向量
int hst[4][2] = {{0,0},{1,2},{3,4},{5,6}},tmp[9],mn,h,t;                    //表面呈现某一种颜色的状态
state q[MX];                                                                //循环队列

using namespace std;

inline int rehash(state a)                                                  //重新获得哈希值
{
    int hsn=0;
    for(int i=0; i<=8; i++)hsn+=a.x[i]*seven[i];
    return hsn;
}
inline char rot(char st,int v)                                              //返回状态 st 的方块按向量 v 滚动后的状态
{
    if(v==1||v==2)return ynxt[(int)st];
    else if(v==3||v==4)return xnxt[(int)st];
    return 0;
}
inline bool mov(state *a,int v)                                             //将方块滚动即：交换空格和方块，这里是将状态 a 更新为：空格按向量 v 平移后的状态
{
    int x=a->blank%3,y=a->blank/3,bpos=a->blank;
    int nx=x+vec[v][1],ny=y+vec[v][2];
    int nxt=ny*3+nx;
    if(nx>2||nx<0||ny>2||ny<0)return 0;
    a->hs-=a->x[nxt]*seven[nxt];                                            //减去滚动方块原来位置对应的 hash 值，接着在下面第二行加上新的 hash 值，避免为了更新 hash 值而调用 rehash()，简化运算，节约时间
    swap(a->x[bpos],a->x[nxt]);
    a->x[bpos]=rot(a->x[bpos],v),a->hs+=a->x[bpos]*seven[bpos],a->step++,a->blank=nxt;
    return 1;
}
void build()                                                                //正向广搜的输入及初始化
{
    int x0,y0;
    h=t=1;
    scanf("%d%d",&x0,&y0);
    if(x0==0&&y0==0)exit(0);
    q[h].blank=(y0-1)*3+x0-1;
    for(int i=0; i<=8; i++)q[h].x[i]=1;
    q[h].x[q[h].blank]=0,q[h].step=0,q[h].hs=rehash(q[h]);
    hsmap[q[1].hs]=0;
}
void dfs(int pos,int bpos)                                                  //用深搜的方式获得逆向广搜的初始状态
{
    if(pos==9)
    {
        memmove(q[++h].x,nowwork,sizeof(nowwork));
        q[h].blank=bpos,q[h].hs=rehash(q[h]),q[h].step=0;
        if(hsmap[q[h].hs]>=0)mn=min(mn,(int)hsmap[q[h].hs]);
        else hsmap[q[h].hs]=-2;
        return;
    }
    if(pos==bpos)nowwork[pos]=0,dfs(pos+1,bpos);
    else for(int i=0; i<=1; i++)nowwork[pos]=hst[tmp[pos]][i],dfs(pos+1,bpos);
}
void in()                                                                   //逆向广搜的输入和初始化
{
    int bpos;
    char ch;
    h=0,t=1;
    for(int i=0; ch=getchar(),i<=8; i++)
    {
        while(ch!='W'&&ch!='E'&&ch!='B'&&ch!='R')ch=getchar();
        if(ch=='W')tmp[i]=1;
        else if(ch=='R')tmp[i]=2;
        else if(ch=='B')tmp[i]=3;
        else tmp[i]=0,bpos=i;
    }
    dfs(0,bpos);                                                            //调用深搜获得所有初始状态并保存到队列里。
}
void sch()                                                                  //正向广搜
{
    state now,nxt;
    memset(hsmap,0xff,sizeof(hsmap));
    build();
    while(h>=t)
    {
        now=q[(t++)%MX];
        if(now.step>=FM)break;
        for(int i=1; nxt=now,i<=4; i++)
        {
            if(mov(&nxt,i)==0)continue;
            if(hsmap[nxt.hs]>=0)continue;
            hsmap[nxt.hs]=nxt.step;
            q[(++h)%MX]=nxt;
        }
    }
}
void check()                                                                //逆向广搜
{
    mn=MX;
    state now,nxt;
    in();
    while(h>=t)
    {
        now=q[(t++)%MX];
        if(now.step>=BM||now.step>=mn)continue;
        for(int i=1; nxt=now,i<=4; i++)
        {
            if(mov(&nxt,i)==0)continue;
            if(hsmap[nxt.hs]==-2)continue;
            if(hsmap[nxt.hs]>=0)mn=min(mn,(int)hsmap[nxt.hs]+nxt.step);
            hsmap[nxt.hs]=-2;
            q[(++h)%MX]=nxt;
        }
    }
    cout<<(mn==MX?-1:mn)<<endl;
}
int main()
{
    while(1)sch(),check();
}