|
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by—cxlove 三阶魔方还原。因为只搜5层，所以使用IDA*搜索。由于每次旋转，每面中心颜色总不变，也就确定了最终的状态，找出每个面中与中间颜色不同的个数的最大值，其中每次旋转会更改每个面的3个位置的颜色，所以 就是（最大值+2）/3。 总共有12种旋转，找到其中的对应方式，使用转动数组就非常方便了，不过数组的初始化是相当蛋疼的工作，最好手头有个三阶魔方。顺时针与逆时针刚好对应。
#include
#include
#include
using namespace std;
//表示每个面除中间的另外8个的位置
short int cen[6][8]={
{0,1,2,3,5,6,7,8},{9,10,11,21,23,33,34,35},{12,13,14,24,26,36,37,38},
{15,16,17,27,29,39,40,41},{18,19,20,30,32,42,43,44},{45,46,47,48,50,51,52,53}
};
//转换数组，12种变换，两两对应，每次转换会更改20个位置
short int change[12][20]={
{11,23,35,34,33,21,9,10,51,48,45,36,24,12,6,3,0,20,32,44},
{9,10,11,23,35,34,33,21,36,24,12,6,3,0,20,32,44,51,48,45},
{14,13,26,38,37,36,24,12,45,46,47,39,27,15,8,7,6,11,23,35},
{12,24,13,14,26,38,37,36,39,27,15,8,7,6,11,23,35,45,46,47},
{17,29,41,40,39,27,15,16,47,50,53,42,30,18,2,5,8,14,26,38},
{15,16,17,29,41,40,39,27,42,30,18,2,5,8,14,26,38,47,50,53},
{18,19,20,32,44,43,42,30,53,52,51,33,21,9,0,1,2,17,29,41},
{42,30,18,19,20,32,44,43,33,21,9,0,1,2,17,29,41,53,52,51},
{0,1,2,5,8,7,6,3,12,13,14,15,16,17,18,19,20,9,10,11},
{6,3,0,1,2,5,8,7,15,16,17,18,19,20,9,10,11,12,13,14},
{45,46,47,50,53,52,51,48,44,43,42,41,40,39,38,37,36,35,34,33},
{51,48,45,46,47,50,53,52,41,40,39,38,37,36,35,34,33,44,43,42}
};
char a[54]; //初始状态
int depth; //迭代加深搜索的层数
bool flag; //是否有解
int centre[6]={4,22,25,28,31,49};//每个面中心坐标
int get_h(char *maze){
int ret=0;
for(int i=0;i |