PKU 2286 The Rotation Game 题解

因为状态很难储存
所以款搜是不可以的
这个题从网上学了一个好的算法
用迭代深搜。每次卡一个深度然后去dfs
这样搜到解的时候就是那个卡的深度了。
知道方法后很简单

#include <string.h>
2

#include <stdio.h>
3

const int N = 25;
4

int a[N], ans[100];
5

#define Max(a, b) ((a)>(b)?(a):(b))
6

int f[8][7][2] = {
7

{ {1,23}, {3,1}, {7,3}, {12,7}, {16,12}, {21,16}, {23,21} },
8

{ {2,24}, {4,2}, {9,4}, {13,9}, {18,13}, {22,18}, {24,22} },
9

{ {11,5}, {10,11}, {9,10}, {8,9}, {7,8}, {6,7}, {5,6} },
10

{ {20,14}, {19,20}, {18,19}, {17,18}, {16,17}, {15,16}, {14,15} },
11

{ {24,2}, {22,24}, {18,22}, {13,18}, {9,13}, {4,9}, {2,4} },
12

{ {23,1}, {21,23}, {16,21}, {12,16}, {7,12}, {3,7}, {1,3} },
13

{ {14,20}, {15,14}, {16,15}, {17,16}, {18,17}, {19,18}, {20,19} },
14

{ {5,11}, {6,5}, {7,6}, {8,7}, {9,8}, {10,9}, {11,10} }
15

};
16

int L, ANS;
17

int check()
18

{
19

int ll = a[7];
20

if(a[8]!=ll || a[9]!=ll || a[12]!=ll || a[13]!=ll ||
21

a[16]!=ll || a[17]!=ll || a[18]!=ll)
22

return 0;
23

return ANS = ll;
24

}
25

int cal()
26

{
27

int num[4];
28

memset(num, 0, sizeof(num));
29

for(int i=7;i<=9;i++)num[a[i]]++;
30

for(int i=12;i<=13;i++)num[a[i]]++;
31

for(int i=16;i<=18;i++)num[a[i]]++;
32

return 8-Max(num[3], Max(num[2], num[1]));
33

}
34

int di(int now)
37

{
38

int i, b[N], j, t;
39

if(now == L)return check();
40

int c = cal();
41

if(now + c > L)return 0;
42

for(i = 0; i < 8; ++i)
43

{
44

ans[now] = i;
45

memcpy(b, a, sizeof(a));
46

for(j = 0; j < 7; ++j) a[f[i][j][1]] = b[f[i][j][0]];
47

t = di(now+1);
48

memcpy(a, b, sizeof(b));
49

if(t != 0) return t;
50

}
51

return 0;
52

}
53

int main() {
55

int i, t;
56

while(scanf("%d", &a[1]), a[1])
57

{
58

for(i = 2; i <= 24; ++i)scanf("%d", &a[i]);
59

if(check() != 0)
60

{
61

printf("No moves needed\n%d\n", a[7]);
62

continue;
63

}
64

L = 1;
65

while( (t = di(0)) == 0)L++;
66

for(i=0; i<L; ++i)putchar(ans[i]+'A');
67

printf("\n%d\n", ANS);
68

}
69

return 0;
70

}
71

posted on 2008-07-19 20:20 gong 阅读(1090) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。




网站导航: 博客园博客园最新博文博问管理

2008年7月

日

一

二

三

四

五

六

统计

随笔 - 50
文章 - 0
评论 - 22
引用 - 0

常用链接

留言簿(6)

随笔档案

搜索

积分与排名

积分 - 29954
排名 - 669