青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

PKU 2286 The Rotation Game 題解

因為狀態很難儲存
所以款搜是不可以的
這個題從網上學了一個好的算法
用迭代深搜。每次卡一個深度然后去dfs
這樣搜到解的時候就是那個卡的深度了。
知道方法后很簡單

 1#include <string.h>
 2#include <stdio.h>
 3const int N = 25;
 4int a[N], ans[100];
 5#define Max(a, b) ((a)>(b)?(a):(b))
 6int 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};
16int L, ANS;
17int 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}
25int 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
35
36int 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
54int 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
72

posted on 2008-07-19 20:20 gong 閱讀(1074) 評論(0)  編輯 收藏 引用

只有注冊用戶登錄后才能發表評論。

網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理

Powered by:
C++博客
Copyright © gong

導航

• C++博客
• 首頁
• 新隨筆
• 聯系
• 聚合
• 管理

統計

• 隨筆 - 50
• 文章 - 0
• 評論 - 22
• 引用 - 0

常用鏈接

• 我的隨筆
• 我的評論
• 我參與的隨筆

留言簿(6)

• 給我留言
• 查看公開留言
• 查看私人留言

隨筆檔案

• 2009年7月 (11)
• 2008年8月 (1)
• 2008年7月 (38)

搜索

積分與排名

• 積分 - 28879
• 排名 - 674

最新評論

閱讀排行榜

評論排行榜