考察:IDA*
思路:
预估函数比较好想,可以发现每次移动都是让一个数字进一个数字出.所以预估函数 = 8-最大的相同数字出现次数.
字典序就操作按字典序枚举,那么第一个答案就是字典序最优的答案.
每次dfs枚举操作,如果一个个if else 写代码很冗长.所以可以人工打表,将A~H操作的下标预处理出.要检查的范围也可以用数组预存.一个很好的技巧是按循环移动顺序预处理op数组,也就是A-F,B-E等对称操作不要写一样顺序的下标.
但是这样还是需要剪枝.这里比较明显(我没想到) 的剪枝是上一个操作是A,下一个操作就没必要是F.回溯的时候也没必要用memcpy,直接反向操作即可.
注意预估函数是返回最小步数,所以不代表步数最多是8.
1 #include <iostream> 2 #include <cstring> 3 #include <vector> 4 using namespace std; 5 const int N = 30,M = 8; 6 int n,mp[N],cnt,depth; 7 int op[M][M] = { 8 {1,3,7,12,16,21,23}, 9 {2,4,9,13,18,22,24}, 10 {11,10,9,8,7,6,5}, 11 {20,19,18,17,16,15,14}, 12 {24,22,18,13,9,4,2}, 13 {23,21,16,12,7,3,1}, 14 {14,15,16,17,18,19,20}, 15 {5,6,7,8,9,10,11} 16 }; 17 int nums[8] = {7,8,9,12,13,16,17,18}; 18 int pre[8] = {5,4,7,6,1,0,3,2},cnts[4],path[N]; 19 int h() 20 { 21 int maxn = 0; 22 memset(cnts,0,sizeof cnts); 23 for(int i=0;i<8;i++) 24 { 25 cnts[mp[nums[i]]]++; 26 if(cnts[mp[nums[i]]]>maxn) maxn = cnts[mp[nums[i]]]; 27 } 28 return 8-maxn; 29 } 30 void moves(int idx) 31 { 32 int t = mp[op[idx][0]]; 33 for(int i=1;i<7;i++) 34 mp[op[idx][i-1]] = mp[op[idx][i]]; 35 mp[op[idx][6]] = t; 36 } 37 bool dfs(int step,int last) 38 { 39 int val = h(); 40 if(step+val>depth) return 0; 41 if(!val) return 1; 42 for(int i=0;i<8;i++) 43 { 44 if(last==pre[i]) continue; 45 moves(i); 46 path[step] = i; 47 if(dfs(step+1,i)) return 1; 48 moves(pre[i]); 49 } 50 return 0; 51 } 52 int main() 53 { 54 while(scanf("%d",&mp[1])&&mp[1]) 55 { 56 cnt = depth = 0; 57 for(int i=2;i<=24;i++) scanf("%d",&mp[i]); 58 while(!dfs(0,-1)) depth++; 59 if(!depth) puts("No moves needed"); 60 else{ 61 for(int i=0;i<depth;i++) printf("%c",path[i]+‘A‘); 62 printf("\n"); 63 } 64 printf("%d\n",mp[8]); 65 } 66 return 0; 67 }