AcWing 181. 回转游戏

原题链接

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

 

上一篇:MAC通过Shell命令脚本监听端口是否挂掉,重启端口


下一篇:781. 森林中的兔子