[HDU1667]The Rotation Game 作者: rin 时间: August 5, 2016 分类: Algo [http://acm.hdu.edu.cn/showproblem.php?pid=1667](http://acm.hdu.edu.cn/showproblem.php?pid=1667 "http://acm.hdu.edu.cn/showproblem.php?pid=1667") [http://bailian.openjudge.cn/practice/2286](http://bailian.openjudge.cn/practice/2286 "http://bailian.openjudge.cn/practice/2286") ![1667-1[1].jpg](https://static.lo-li.net/typecho/2016/10/2404773207.jpg) ###问题描述 现有一块有24个格子的井字板子，每个格子用1、2或3标记，每种格子各有8个。 起初这些格子分布随机，你需要通过A-H 8种操作将中心8个格子作变为相同的标记。 （图中使用A操作将A列向上拉了一格，C操作将C列向右拉了一列，中心变为2） ###输入 有多组数据$$(\leq 30)$$，每组数据包含一行24个数字，代表从左上到右下24个格子的初始状态。输入0代表结束。 ###输出 每组数据包含两行，第一行是最佳的操作顺序，第二行是此时中心的字符。若不需要操作，即初始时中心八个字符就相同，则输出`No moves needed`，（**也要输出中心字符**） 最佳操作顺序为：操作次数最少。同次数若有多种则为字典序小者 <!--more--> [](http://lo-li.net/wp-content/uploads/2016/08/HDU1167TheRotationGame1.png) 将板子如上图编号存下来，操作A-H编号为0-7 ```cpp //http://bailian.openjudge.cn/practice/2286/ //http://bailian.openjudge.cn/2016acmmid/e/ #include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <memory.h> using namespace std; #define INF 0x3f3f3f3f const int indexs[8][7] = { // 每种操作变动的下标 { 0,2,6,11,15,20,22 }, //AF { 1,3,8,12,17,21,23 }, //BE { 10,9,8,7,6,5,4 }, //CH { 19,18,17,16,15,14,13 }, //DG { 23,21,17,12,8,3,1 }, //EB { 22,20,15,11,6,2,0 }, //FA { 13,14,15,16,17,18,19 }, //GD { 4,5,6,7,8,9,10 }, //HC }; const int reverseOp[] = { 5,4,7,6,1,0,3,2,-1 }; // A-H的逆操作 const int center[] = { 6,7,8,11,12,15,16,17 }; // 中心八点下标 int min(int a, int b) { return a>b ? b : a; } int max(int a, int b) { return a<b ? b : a; } char map[24]; char route[101]; // 操作序列 bool hasSolution; ``` 执行某一个操作只需将那一列/行每格顺序往后挪 ```c++ void pull(int op) { int tmp = map[indexs[op][0]]; for (int i = 0; i < 7 - 1; i++) { map[indexs[op][i]] = map[indexs[op][i + 1]]; } map[indexs[op][6]] = tmp; } ``` 估价函数，找出当前局面下使得中心点变成1、2和3所需的**最小**步数。因为总共就3个数，一次任何一种操作只会改变中间一种数字的数量，用8减去数量最多那个数字的**个数**即为最小步数 ```c++ int h() { int cnt[3] = { 0,0,0 }; // 计数 1, 2, 3 int maxCnt = -1; for (int i = 0; i < 8; i++) { cnt[map[center[i]] - 1]++; maxCnt = max(maxCnt, cnt[map[center[i]] - 1]); } return 8 - maxCnt; } ``` 搜索 - 迭代加深：保证第一次搜到的解是最短的 - 从A操作到H操作搜，保证字典序最小 - 可行性剪枝：当前深度（已操作的次数）+估价函数值= （至少还需要的步数）若大于当前规定的最大深度（最多步数）则剪枝 - 相邻操作不为互逆操作 ```c++ void d(int depth, int lastOp, int maxDepth) {// 当前深度、到达当前深度所做的操作 if (hasSolution)return; if (h() == 0) { // 中心都相同了 hasSolution = true; route[depth] = '\0'; printf("%s\n%d\n",route, map[center[0]]); return; } if (depth > maxDepth || depth + h() > maxDepth) return; // 可行性剪枝 for (int nextOp = 0; nextOp < 8; nextOp++) { if (nextOp != reverseOp[lastOp]) { //操作不互逆 pull(nextOp); route[depth] = nextOp + 'A'; d(depth + 1, nextOp, maxDepth); pull(reverseOp[nextOp]); //还原 } } } int main() { while (1) { for (int i = 0; i < 24; i++) { scanf("%d", &map[i]); if (map[i] == 0) return 0; } hasSolution = false; if (h() == 0) { printf("No moves needed\n%d\n", map[center[0]]); continue; } for (int depth = 1; !hasSolution; depth++) { // 迭代加深 d(0, 8, depth); } } return 0; } ``` 标签: DFS, IDA*, 迭代加深
666，看了这个博客才感觉学到了东西，希望博主加油！！！
感觉h表控制搜索方向的优势在这题里面展现不出来，就是IDA，希望博主推荐一下那方面的题，我学习一下。