题意:把由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