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

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

思路:由于这道题类似于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();
}

分类: 所有

1 条评论

konnyakuxzy · 2017年5月11日 3:39 下午

Orz您不return 0(手动高亮)的啊。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *