HDU 3459 Rubik 2×2×2 二阶魔方还原(IDA*)
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
二阶魔方还原，已经好复杂，好抽象了。
题目不要求最短的，不过IDA*写出的应该是最短的吧，而且是字典序最小的。
先说一下这个二阶魔方的一个特点，虽然有3种旋转，但是总有一块是不动的，就是后面靠左靠下的那个，既然不动，魔方其中3个面的颜色就确定了，通过这三个面的颜色就可以确定其它3个面的颜色。
这样就可以得到一个估价函数H，不过实在是太弱的剪枝了。6个面的颜色都有，就可以根据这个找到有几个位置上的和目标不同，每次旋转可以改变8个位置，也就是（总数+7）/8；
代码写得很坑爹，不过我估计这也没办法，看别人代码也挺长的，不过效率差别好大，继续想剪枝。
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<string>#include<vector>#include<algorithm>#include<map>#include<set>#define inf 1<<30using namespace std;struct Node{int x,y;}block[8][3],side[6][4];//记录魔方的八个立方体的三个面,每个面的4个坐标char str[10][10];char each_col[6]; //每个面的颜色，分别为上，左，前，右，后，下bool flag;int ans[100];int depth;void Init(){ //获得每个立方体的每个面坐标,以及魔方每个面各个点的坐标block[0][0].x=3;block[0][0].y=2;block[0][1].x=3;block[0][1].y=1;block[0][2].x=4;block[0][2].y=2;block[1][0].x=3;block[1][0].y=3;block[1][1].x=3;block[1][1].y=4;block[1][2].x=4;block[1][2].y=3;block[2][0].x=2;block[2][0].y=2;block[2][1].x=2;block[2][1].y=1;block[2][2].x=1;block[2][2].y=2;block[3][0].x=2;block[3][0].y=3;block[3][1].x=1;block[3][1].y=3;block[3][2].x=2;block[3][2].y=4;block[4][0].x=3;block[4][0].y=0;block[4][1].x=5;block[4][1].y=2;block[4][2].x=3;block[4][2].y=7;block[5][0].x=5;block[5][0].y=3;block[5][1].x=3;block[5][1].y=5;block[5][2].x=3;block[5][2].y=6;block[6][0].x=0;block[6][0].y=2;block[6][1].x=2;block[6][1].y=7;block[6][2].x=2;block[6][2].y=0;block[7][0].x=0;block[7][0].y=3;block[7][1].x=2;block[7][1].y=5;block[7][2].x=2;block[7][2].y=6;side[0][0].x=0;side[0][0].y=2;side[0][1].x=0;side[0][1].y=3;side[0][2].x=1;side[0][2].y=2;side[0][3].x=1;side[0][3].y=3;side[1][0].x=2;side[1][0].y=0;side[1][1].x=2;side[1][1].y=1;side[1][2].x=3;side[1][2].y=0;side[1][3].x=3;side[1][3].y=1;side[2][0].x=2;side[2][0].y=2;side[2][1].x=2;side[2][1].y=3;side[2][2].x=3;side[2][2].y=2;side[2][3].x=3;side[2][3].y=3;side[3][0].x=2;side[3][0].y=4;side[3][1].x=2;side[3][1].y=5;side[3][2].x=3;side[3][2].y=4;side[3][3].x=3;side[3][3].y=5;side[4][0].x=2;side[4][0].y=6;side[4][1].x=2;side[4][1].y=7;side[4][2].x=3;side[4][2].y=6;side[4][3].x=3;side[4][3].y=7;side[5][0].x=4;side[5][0].y=2;side[5][1].x=4;side[5][1].y=3;side[5][2].x=5;side[5][2].y=2;side[5][3].x=5;side[5][3].y=3;}char get_color(int A,int B,int C){ //获得每个面的颜色，通过其中的3个面for(int i=0;i<8;i++){if(str[block[i][0].x][block[i][0].y]==each_col[A]&&str[block[i][1].x][block[i][1].y]==each_col[B]&&str[block[i][2].x][block[i][2].y]!=each_col[C])return str[block[i][2].x][block[i][2].y];if(str[block[i][1].x][block[i][1].y]==each_col[A]&&str[block[i][0].x][block[i][0].y]==each_col[B]&&str[block[i][2].x][block[i][2].y]!=each_col[C])return str[block[i][2].x][block[i][2].y];if(str[block[i][0].x][block[i][0].y]==each_col[A]&&str[block[i][2].x][block[i][2].y]==each_col[B]&&str[block[i][1].x][block[i][1].y]!=each_col[C])return str[block[i][1].x][block[i][1].y];if(str[block[i][2].x][block[i][2].y]==each_col[A]&&str[block[i][0].x][block[i][0].y]==each_col[B]&&str[block[i][1].x][block[i][1].y]!=each_col[C])return str[block[i][1].x][block[i][1].y];if(str[block[i][1].x][block[i][1].y]==each_col[A]&&str[block[i][2].x][block[i][2].y]==each_col[B]&&str[block[i][0].x][block[i][0].y]!=each_col[C])return str[block[i][0].x][block[i][0].y];if(str[block[i][2].x][block[i][2].y]==each_col[A]&&str[block[i][1].x][block[i][1].y]==each_col[B]&&str[block[i][0].x][block[i][0].y]!=each_col[C])return str[block[i][0].x][block[i][0].y];}}void change_x(char maze[10][10]){ //x轴旋转char tmp;tmp=maze[2][4];maze[2][4]=maze[2][5];maze[2][5]=maze[3][5];maze[3][5]=maze[3][4];maze[3][4]=tmp;tmp=maze[1][3];maze[1][3]=maze[2][6];maze[2][6]=maze[5][3];maze[5][3]=maze[3][3];maze[3][3]=tmp;tmp=maze[0][3];maze[0][3]=maze[3][6];maze[3][6]=maze[4][3];maze[4][3]=maze[2][3];maze[2][3]=tmp;}void change_y(char maze[10][10]){ //y轴旋转char tmp;tmp=maze[2][0]; maze[2][0]=maze[2][6];maze[2][6]=maze[2][4]; maze[2][4]=maze[2][2]; maze[2][2]=tmp;tmp=maze[2][1]; maze[2][1]=maze[2][7];maze[2][7]=maze[2][5]; maze[2][5]=maze[2][3]; maze[2][3]=tmp;tmp=maze[0][2]; maze[0][2]=maze[0][3];maze[0][3]=maze[1][3]; maze[1][3]=maze[1][2]; maze[1][2]=tmp;}void change_z(char maze[10][10]){ //z轴旋转char tmp;tmp=maze[2][1]; maze[2][1]=maze[1][3];maze[1][3]=maze[3][4]; maze[3][4]=maze[4][2]; maze[4][2]=tmp;tmp=maze[3][1]; maze[3][1]=maze[1][2];maze[1][2]=maze[2][4]; maze[2][4]=maze[4][3]; maze[4][3]=tmp;tmp=maze[2][2]; maze[2][2]=maze[2][3];maze[2][3]=maze[3][3]; maze[3][3]=maze[3][2]; maze[3][2]=tmp;}int get_h(char maze[10][10]){ int ret=0;for(int i=0;i<6;i++){for(int j=0;j<4;j++)if(maze[side[i][j].x][side[i][j].y]!=each_col[i])ret++;}return (ret+7)/8;};void IDAstar(char maze[10][10],int tmp_depth){if(flag)return;if(get_h(maze)>tmp_depth)return;if(tmp_depth==0){flag=true;return;}for(int i=0;i<3;i++){if(flag)return;char temp[10][10];for(int i=0;i<6;i++)for(int j=0;j<8;j++)temp[i][j]=maze[i][j];if(i==0)change_x(temp);else if(i==1)change_y(temp);else change_z(temp);ans[tmp_depth]=i;IDAstar(temp,tmp_depth-1);}}int main(){Init();while(scanf("%s",str[0])!=EOF){for(int i=1;i<6;i++)scanf("%s",str[i]);if(strcmp(str[2],"........")==0)break;each_col[1]=str[3][0];each_col[5]=str[5][2];each_col[4]=str[3][7];//其中有一个方块一直没有动，可以确定最终结果的3个面的颜色each_col[0]=get_color(1,4,5);each_col[2]=get_color(1,5,4);each_col[3]=get_color(4,5,1);flag=false;for(depth=get_h(str);;depth++){IDAstar(str,depth);if(flag){for(int i=depth;i>0;i--)printf("%c",ans[i]+'X');printf("\n");break;}}}return 0;}