学步园

题意：

初始状态固定（朝上的全是W，空格位置输入给出），输入初始状态的空格位置，和最终状态朝上的位置，输出要多少步才能移动到，超过30步输出-1.

简析：

每一个格子有6种状态，分别是

0WRB, 1WBR, 2RWB, 3RBW, 4BRW, 5BWR （上前后 对应的颜色）

由于只给出了终态朝上的颜色，其他的不知道，所以终态真正应该有256种，对于这个可以用一次dfs全部枚举出。

一、

搜索策略的问题

单向搜索的话，平均一下，大概每次也有3个状态，30层的话，复杂度太高，放弃。

A*的话，考虑当前不在正确位置的格子数。不知道是否可行，没有尝试。

双向搜索的话，只有30层，平分一下15层，再看看时间5s，还是可以接受的。而考虑到最终状态有256个，所以反向扩展的速度非常快，所以我们可以让

反向搜索只进行10层左右，保持2边平衡达到最佳速度。

二、

考虑判重的问题

由上面的分析可知，判重可以选择2种方式。

1、用一个6进制可以存下所有非空格的情况，再加一个空格的位置也就是6^8*9=15116544这么大的数组，双向搜索的话，也就是这个的2倍大的数组。

2、用一个7进制存下所有情况7^9-1=40353607，双向搜索的话，就是2倍………接近1亿。

第二种果断放弃了。。。

三、

hash值计算的问题

显然初始情况的hash要 s[0]*6^0+s[1]*6^1+......，但如果以后每次我们都用一个for(0---9)的循环计算的话，时间复杂度太高。

分析后发，每移动一次，左右移动的话，只会改变1个位置的值，上下移动的话只会改变3个位置的值，所以我们就计算这几个改变的值就够了。

四、

STL的使用，我测试了一下，不用STL的话速度可以快1000ms左右，但是内存就不好把握了，在上面都考虑到的情况下，用STL也不会影响AC。

给出STL版本的

include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;            // 0WRB, 1WBR, 2RWB, 3RBW, 4BRW, 5BWR

int base[]={1,6,36,216,1296,7776,46656,279936,1679616};
int state[6][4]={{2,2,4,4},{5,5,3,3},{0,0,5,5},{4,4,1,1},{3,3,0,0},{1,1,2,2}};
char hash1[1680000][9];
char hash2[1680000][9];
char b[10];
struct node
{
    int s[9];
    int dis;
    int space;
    int value;
}st;
queue<node> q;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};      //下，上，右，左，和前面相反

inline bool isok(int &x,int &y)
{
    return x>=0&&x<3&&y>=0&&y<3;
}
inline int cal(node &t)     //计算初始的hash值
{
    int value=0;
    int top=0;
    for(int i=0;i<9;i++)
    {
        if(i==t.space) continue;
        value+=t.s[i]*base[top++];
    }
    return value;
}
 int cal(node &t,node &f,int d)     //因为每次移动只会改变几个hash值，所以可以特判
{
    if(d==2)
    {
        t.value-=f.s[t.space]*base[f.space];
        t.value+=t.s[f.space]*base[f.space];
        return t.value;
    }
    else if(d==3)
    {
        t.value-=f.s[t.space]*base[t.space];
        t.value+=t.s[f.space]*base[t.space];
        return t.value;
    }
    else if(d==0)
    {
        for(int i=f.space;i<=f.space+2;i++)
        {
            t.value-=f.s[i+1]*base[i];
            t.value+=t.s[i]*base[i];
        }
        return t.value;
    }
    else if(d==1)
    {
        for(int i=t.space;i<=t.space+2;i++)
        {
            t.value-=f.s[i]*base[i];
            t.value+=t.s[i+1]*base[i];
        }
        return t.value;
    }
}
bool bfs(node st)
{
    node t1,t2,f;
    queue<node> Q;
    st.dis=0;
    Q.push(st);
    t2.dis=0;
    int k;
    int k1=1,kk1=0,k2=256,kk2=0;
    while(!Q.empty()&&!q.empty())
    {
        while(k1--){
        st=Q.front();Q.pop();
        if(st.dis+1+t2.dis>30) {printf("-1\n");return false;}
        for(int d=0;d<4;d++)
        {
            t1=st;
            int sx=t1.space/3;
            int sy=t1.space%3;
            int nx=sx+dir[d][0];
            int ny=sy+dir[d][1];
            if(isok(nx,ny))
            {
                t1.space=nx*3+ny;
                t1.s[sx*3+sy]=state[t1.s[nx*3+ny]][d];
                t1.s[nx*3+ny]=6;
                t1.dis=st.dis+1;
                t1.value=cal(t1,st,d);
                if(hash1[t1.value][t1.space]) continue;
                if(hash2[t1.value][t1.space]) {printf("%d\n",t1.dis+t2.dis);return true;}

                hash1[t1.value][t1.space]=t1.dis;
                Q.push(t1);
                kk1++;
            }
        }
        }
        k1=kk1;
        kk1=0;
        while(k2--){
        f=q.front();
        if(f.dis==9) break;
        q.pop();
        for(int d=0;d<4;d++)
        {
            t2=f;
            int sx=t2.space/3;
            int sy=t2.space%3;
            int nx=sx+dir[d][0];
            int ny=sy+dir[d][1];
            t2.dis=f.dis+1;
            if(isok(nx,ny))
            {
                t2.space=nx*3+ny;
                t2.s[sx*3+sy]=state[t2.s[nx*3+ny]][d];
                t2.s[nx*3+ny]=6;
                t2.value=cal(t2,f,d);
                if(hash2[t2.value][t2.space]) continue;
                if(hash1[t2.value][t2.space])
                {
                    printf("%d\n",t2.dis+st.dis+1);
                    return true;
                }
                hash2[t2.value][t2.space]=t2.dis;
                q.push(t2);
                kk2++;
            }
        }
        }
        t1.dis=f.dis+1;
        k2=kk2;
        kk2=0;
    }
    printf("-1\n");
}
void dfs(node &end,int k)
{
    if(k==9)
    {
        end.dis=0;
        end.value=cal(end);
        q.push(end);
        hash2[end.value][end.space]=1;
        return;
    }
    if(b[k]=='W')
    {
        end.s[k]=0;
        dfs(end,k+1);
        end.s[k]=1;
        dfs(end,k+1);
    }
    else if(b[k]=='R')
    {
        end.s[k]=2;
        dfs(end,k+1);
        end.s[k]=3;
        dfs(end,k+1);
    }
    else if(b[k]=='B')
    {
        end.s[k]=4;
        dfs(end,k+1);
        end.s[k]=5;
        dfs(end,k+1);
    }
    else
    {
        end.s[k]=6;
        dfs(end,k+1);
    }
}
int main()
{
    int x,y;
    char a;
    node end;
    while(scanf("%d%d",&y,&x)!=EOF)
    {
        if(!x&&!y) break;
        while(!q.empty()) q.pop();
        memset(hash1,0,sizeof(hash1));
        memset(hash2,0,sizeof(hash2));

        x--;y--;
        for(int i=0;i<9;i++)
        {
            if(x==i/3&&y==i%3) {st.s[i]=6;st.space=i;}
            else st.s[i]=0;
        }
        for(int i=0;i<9;i++)
        {
            scanf(" %c",&a);
            if(a=='E') end.space=i;
            b[i]=a;
        }
        dfs(end,0);     //得到所有的终点状态，全部加入队列。

        int k;          //一开始就是答案
        st.value=cal(st);
        hash1[st.value][st.space]=-1;
        if(hash2[st.value][st.space]) {printf("0\n");continue;}
        bfs(st);
    }
    return 0;
}

再给出静态数组版本