考察: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 }