题目链接：
思路：大牛说是IDA*的入门题=.=构造h()=8-max(1,2,3); max(1,2,3)表示中间的八个位置中出现最多的数的个数。 因为每次操作只能改变中间8个中的一个，所以可以这样构造启发式函数。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 int map[10][10]; 8 int maxdeep; 9 char ans[111]; 10 11 bool Judge() 12 { 13 if(map[3][3]!=map[3][4])return false; 14 if(map[3][3]!=map[3][5])return false; 15 if(map[3][3]!=map[4][3])return false; 16 if(map[3][3]!=map[4][5])return false; 17 if(map[3][3]!=map[5][3])return false; 18 if(map[3][3]!=map[5][4])return false; 19 if(map[3][3]!=map[5][5])return false; 20 return true; 21 } 22 23 int Get_H() 24 { 25 int MAX=0,pos[4]={ 0}; 26 for(int i=3;i<=5;i++){ 27 pos[map[i][3]]++; 28 pos[map[i][5]]++; 29 } 30 pos[map[3][4]]++; 31 pos[map[5][4]]++; 32 for(int i=1;i<=3;i++)MAX=max(MAX,pos[i]); 33 return 8-MAX; 34 } 35 36 void Move_A() 37 { 38 int tmp=map[1][3]; 39 for(int i=2;i<=7;i++)map[i-1][3]=map[i][3]; 40 map[7][3]=tmp; 41 } 42 43 void Move_B() 44 { 45 int tmp=map[1][5]; 46 for(int i=2;i<=7;i++)map[i-1][5]=map[i][5]; 47 map[7][5]=tmp; 48 } 49 50 void Move_C() 51 { 52 int tmp=map[3][7]; 53 for(int i=7;i>=2;i--)map[3][i]=map[3][i-1]; 54 map[3][1]=tmp; 55 } 56 57 void Move_D() 58 { 59 int tmp=map[5][7]; 60 for(int i=7;i>=2;i--)map[5][i]=map[5][i-1]; 61 map[5][1]=tmp; 62 } 63 64 void Move_E() 65 { 66 int tmp=map[7][5]; 67 for(int i=7;i>=2;i--)map[i][5]=map[i-1][5]; 68 map[1][5]=tmp; 69 } 70 71 void Move_F() 72 { 73 int tmp=map[7][3]; 74 for(int i=7;i>=2;i--)map[i][3]=map[i-1][3]; 75 map[1][3]=tmp; 76 } 77 78 void Move_G() 79 { 80 int tmp=map[5][1]; 81 for(int i=2;i<=7;i++)map[5][i-1]=map[5][i]; 82 map[5][7]=tmp; 83 } 84 85 void Move_H() 86 { 87 int tmp=map[3][1]; 88 for(int i=2;i<=7;i++)map[3][i-1]=map[3][i]; 89 map[3][7]=tmp; 90 } 91 92 bool IDA_star(int deep) 93 { 94 if(deep==maxdeep)return Judge(); 95 if(Get_H()+deep>maxdeep)return false; 96 97 ans[deep]='A'; 98 Move_A(); 99 if(IDA_star(deep+1))return true;100 Move_F();101 102 ans[deep]='B';103 Move_B();104 if(IDA_star(deep+1))return true;105 Move_E();106 107 ans[deep]='C';108 Move_C();109 if(IDA_star(deep+1))return true;110 Move_H();111 112 ans[deep]='D';113 Move_D();114 if(IDA_star(deep+1))return true;115 Move_G();116 117 ans[deep]='E';118 Move_E();119 if(IDA_star(deep+1))return true;120 Move_B();121 122 ans[deep]='F';123 Move_F();124 if(IDA_star(deep+1))return true;125 Move_A();126 127 ans[deep]='G';128 Move_G();129 if(IDA_star(deep+1))return true;130 Move_D();131 132 ans[deep]='H';133 Move_H();134 if(IDA_star(deep+1))return true;135 Move_C();136 return false;137 }138 139 140 int main()141 {142 memset(map,0,sizeof(map));143 for(int i=1;i<=7;i++)map[i][3]=map[i][5]=1;144 for(int i=1;i<=7;i++)map[3][i]=map[5][i]=1;145 while(true){146 for(int i=1;i<=7;i++){147 for(int j=1;j<=7;j++){148 if(map[i][j]==0)continue;149 scanf("%d",&map[i][j]);150 if(map[i][j]==0)return 0;151 }152 }153 if(Judge()){154 puts("No moves needed");155 printf("%d\n",map[3][3]);156 continue;157 }158 for(maxdeep=1; ;maxdeep++){159 if(IDA_star(0))break;160 }161 ans[maxdeep]='\0';162 cout< <