首页 > 代码库 > UVa1603 The Rotation Game (IDA*)
UVa1603 The Rotation Game (IDA*)
链接：http://acm.hust.edu.cn/vjudge/problem/36627
分析：感觉这题前面的处理比较麻烦。首先把图中的位置从左到右从上到下编号，然后用一个二维数组记录8个方向上各个位置的编号，枚举最大深度maxd，乐观估计函数为至少需要移动次数，因为每次移动最多改变一个位置上的数字，所以中间8个位置除了出现次数最多的数字外的数字个数为x的话那么就至少要移动x次，枚举move8个方向再递归如果check为true则成功找到解返回，否则将a复位继续枚举，枚举完8个方向找不到解则失败返回false。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 /* 6 00 01 7 02 03 8 04 05 06 07 08 09 10 9 11 1210 13 14 15 16 17 18 1911 20 2112 22 2313 */14 15 const int rev[8] = {5, 4, 7, 6, 1, 0, 3, 2};16 const int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};17 int line[8][7] = {18 {0, 2, 6, 11, 15, 20, 22},19 {1, 3, 8, 12, 17, 21, 23},20 {10, 9, 8, 7, 6, 5, 4},21 {19, 18, 17, 16, 15, 14, 13},22 };23 24 int a[24];25 char ans[1000];26 27 int diff(int target) {28 int cnt = 0;29 for (int i = 0; i < 8; i++)30 if (a[center[i]] != target) cnt++;31 return cnt;32 }33 34 inline int h() {35 return min(min(diff(1), diff(2)), diff(3));36 }37 38 bool check() {39 for (int i = 0; i < 8; i++)40 if (a[center[i]] != a[center[0]]) return false;41 return true;42 }43 44 void move(int i) {45 int tmp = a[line[i][0]];46 for (int j = 0; j < 6; j++) a[line[i][j]] = a[line[i][j + 1]];47 a[line[i][6]] = tmp;48 }49 50 bool dfs(int d, int maxd) {51 if (check()) {52 ans[d] = ‘\0‘;53 printf("%s\n", ans);54 return true;55 }56 if (maxd - d < h()) return false;57 for (int i = 0; i < 8; i++) {58 ans[d] = ‘A‘ + i;59 move(i);60 if (dfs(d + 1, maxd)) return true;61 move(rev[i]);62 }63 return false;64 }65 66 int main() {67 for (int i = 4; i < 8; i++)68 for (int j = 0; j < 7; j++)69 line[i][j] = line[rev[i]][6 - j];70 while (scanf("%d", &a[0]) == 1 && a[0]) {71 for (int i = 1; i < 24; i++) scanf("%d", &a[i]);72 for (int i = 0; i < 24; i++) if (!a[i]) return 0;73 if (check()) printf("No moves needed\n");74 else for (int maxd = 1; ; maxd++)75 if (dfs(0, maxd)) break;76 printf("%d\n", a[6]);77 }78 return 0;79 }
UVa1603 The Rotation Game (IDA*)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。