• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            A Za, A Za, Fighting...

            堅信:勤能補(bǔ)拙

            PKU 1198 Solitaire

            問題:
            http://acm.pku.edu.cn/JudgeOnline/problem?id=1198

            思路:
            寬度優(yōu)先搜索
            tips:
            1. 如何表示整個chessboard?
               最簡單的方法是用二維數(shù)組,不過如果發(fā)現(xiàn)該chessboard是8X8的話,很自然地會想到是否可以用一個整數(shù)來表示
               答案是肯定的,long long類型,不過可能unsigned long long會更合適,避免負(fù)數(shù)產(chǎn)生的影響呵呵

            2. 如何判斷一個狀態(tài)是否被訪問過?
               根據(jù)tips 1,我們使用一個unsigned long long來表示狀態(tài),而如果用一個一維數(shù)組來表示其整個范圍顯然是不合適的
               答案是利用HASH表,額...不是我自己想的,不過這個想法我是應(yīng)該想到的,艾...繼續(xù)加油
               HASH, 相當(dāng)強(qiáng)大而簡單的方案
               這里我是使用鏈接法來解決HASH沖突的

            單向?qū)挾葍?yōu)先搜索
            剛提交的時候一直TLE, 結(jié)果我將HASH_MAX設(shè)置地更大之后,勉勉強(qiáng)強(qiáng)地通過了,汗...
             1 #define BOARD 8
             2 #define MOVE_MAX 8
             3 #define PRIME 100007
             4 #define HASH_MAX PRIME
             5 #define is_set(i, j, state) (state & (((unsigned long long)1)<<((i)*BOARD+(j))))
             6 #define set_bit(i, j, state) (state |= (((unsigned long long)1)<<((i)*BOARD+(j))))
             7 #define clear_bit(i, j, state) (state &= (~(((unsigned long long)1)<<((i)*BOARD+(j)))))
             8 #define is_valid(i, j) (i>=0 && i<BOARD && j>=0 && j<BOARD)
             9 struct Node {
            10     /* 8x8 chessboard can be represented by 64 bits */
            11     unsigned long long state;
            12     short move;
            13 }queue[635376];
            14 unsigned long long begin, end;
            15 const int dx[] = {00-11};
            16 const int dy[] = {-1100};
            17 int head, tail;
            18 struct Hash {
            19     unsigned long long *pstate;
            20     struct Hash *next;
            21 }hash_table[HASH_MAX];
            22 
            23 int
            24 check_hash(unsigned long long value)
            25 {
            26     int index = value % PRIME;
            27     struct Hash *= hash_table[index].next;
            28     while(p != NULL) {
            29         if(*(p->pstate) == value) 
            30             return 1;
            31         p = p->next;
            32     }
            33     return 0;
            34 }
            35 
            36 void
            37 insert_hash(unsigned long long *pstate, int index)
            38 {
            39     struct Hash *node = malloc(sizeof(struct Hash));
            40     node->pstate = pstate;
            41     node->next = hash_table[index].next;
            42     hash_table[index].next = node;
            43 }
            44 
            45 int
            46 bfs()
            47 {
            48     int i, j, x, y, next_x, next_y, cnt, cur_move=0;
            49     unsigned long long cur_state, next_state;
            50     queue[tail].state = begin;
            51     queue[tail].move = 0;
            52     insert_hash(&(queue[tail].state), (queue[tail].state)%PRIME);
            53     while(head<tail && cur_move<=MOVE_MAX) {
            54         ++head;
            55         cnt = 0;
            56         cur_state = queue[head].state;
            57         cur_move = queue[head].move;
            58         if(cur_state == end)
            59             return 1;
            60         for(i=0; i<64 && cnt<4; i++) {
            61             if(cur_state & (((unsigned long long)1)<<i)) {
            62                 ++cnt;
            63                 x = i/BOARD;
            64                 y = i%BOARD; 
            65                 for(j=0; j<4; j++) { /* left, right, up, down */
            66                     next_x = x + dx[j];
            67                     next_y = y + dy[j];
            68                     if(!is_valid(next_x, next_y))
            69                         continue;
            70                     if(is_set(next_x, next_y, cur_state)) {
            71                         next_x += dx[j];
            72                         next_y += dy[j];
            73                         if(!is_valid(next_x, next_y))
            74                             continue;
            75                     }
            76                     /* make sure the next state never showed before */
            77                     /* hash: one of the most powerful tools */
            78                     next_state = cur_state;
            79                     clear_bit(x, y, next_state);
            80                     set_bit(next_x, next_y, next_state);
            81                     if(!check_hash(next_state)) {
            82                         ++tail;
            83                         queue[tail].move = cur_move + 1;
            84                         queue[tail].state = next_state;
            85                         insert_hash(&(queue[tail].state), (queue[tail].state)%PRIME);
            86                     } 
            87                 }
            88             }
            89         }
            90     }
            91     return 0;
            92 }

            雙向?qū)挾葍?yōu)先搜索
            當(dāng)我們知道開始和結(jié)束狀態(tài)的條件下,可以采用雙向?qū)挾葍?yōu)先搜索
            而且可以大大減小需要搜索的狀態(tài)數(shù)目,因為需要搜索的層數(shù)減少一半
              1 /* bidirectional BFS */
              2 /* Memory: 2704K Time: 47MS */
              3 #include<stdio.h>
              4 #include<stdlib.h>
              5 #include<string.h>
              6 
              7 #define BOARD 8
              8 #define MOVE_MAX 8
              9 #define PRIME 10007
             10 #define HASH_MAX PRIME
             11 #define is_set(i, j, state) (state & (((unsigned long long)1)<<((i)*BOARD+(j))))
             12 #define set_bit(i, j, state) (state |= (((unsigned long long)1)<<((i)*BOARD+(j))))
             13 #define clear_bit(i, j, state) (state &= (~(((unsigned long long)1)<<((i)*BOARD+(j)))))
             14 #define is_valid(i, j) (i>=0 && i<BOARD && j>=0 && j<BOARD)
             15 struct Node {
             16     /* 8x8 chessboard can be represented by 64 bits */
             17     unsigned long long state;
             18     short move;
             19 }queue[63537], second_queue[63537];
             20 unsigned long long begin, end;
             21 const int dx[] = {00-11};
             22 const int dy[] = {-1100};
             23 int head, tail, second_head, second_tail;
             24 struct Hash {
             25     unsigned long long *pstate;
             26     struct Hash *next;
             27 }hash_table[HASH_MAX], second_hash_table[HASH_MAX];
             28 
             29 int
             30 check_hash(struct Hash *hash, unsigned long long value)
             31 {
             32     int index = value % PRIME;
             33     struct Hash *= hash[index].next;
             34     while(p != NULL) {
             35         if(*(p->pstate) == value) 
             36             return 1;
             37         p = p->next;
             38     }
             39     return 0;
             40 }
             41 
             42 void
             43 insert_hash(struct Hash *hash, unsigned long long *pstate, int index)
             44 {
             45     struct Hash *node = malloc(sizeof(struct Hash));
             46     node->pstate = pstate;
             47     node->next = hash[index].next;
             48     hash[index].next = node;
             49 }
             50 
             51 int
             52 bfs()
             53 {
             54     int i, j, x, y, next_x, next_y, cnt, cur_move, second_cur_move;
             55     cur_move = second_cur_move = 0;
             56     unsigned long long cur_state, next_state;
             57     queue[tail].state = begin;
             58     queue[tail].move = 0;
             59     insert_hash(hash_table, &(queue[tail].state), (queue[tail].state)%PRIME);
             60     second_queue[second_tail].state = end;
             61     second_queue[second_tail].move = 0;
             62     insert_hash(second_hash_table, &(second_queue[second_tail].state), (second_queue[second_tail].state)%PRIME);
             63     while(head<tail && second_head<second_tail) {
             64         ++head;
             65         cnt = 0;
             66         cur_state = queue[head].state;
             67         cur_move = queue[head].move;
             68         for(i=0; i<64 && cnt<4; i++) {
             69             if(cur_state & (((unsigned long long)1)<<i)) {
             70                 ++cnt;
             71                 x = i/BOARD;
             72                 y = i%BOARD; 
             73                 for(j=0; j<4; j++) { /* left, right, up, down */
             74                     next_x = x + dx[j];
             75                     next_y = y + dy[j];
             76                     if(!is_valid(next_x, next_y))
             77                         continue;
             78                     if(is_set(next_x, next_y, cur_state)) {
             79                         next_x += dx[j];
             80                         next_y += dy[j];
             81                         if(!is_valid(next_x, next_y))
             82                             continue;
             83                     }
             84                     /* make sure the next state never showed before */
             85                     /* hash: one of the most powerful tools */
             86                     next_state = cur_state;
             87                     clear_bit(x, y, next_state);
             88                     set_bit(next_x, next_y, next_state);
             89                     if(!check_hash(hash_table, next_state) && cur_move<MOVE_MAX/2) {
             90                         if(check_hash(second_hash_table, next_state)) 
             91                             return 1;
             92                         ++tail;
             93                         queue[tail].move = cur_move + 1;
             94                         queue[tail].state = next_state;
             95                         insert_hash(hash_table, &(queue[tail].state), (queue[tail].state)%PRIME);
             96                     } 
             97                 }
             98             }
             99         }
            100         ++second_head;
            101         cnt = 0;
            102         cur_state = second_queue[second_head].state;
            103         second_cur_move = second_queue[second_head].move;
            104         for(i=0; i<64 && cnt<4; i++) {
            105             if(cur_state & (((unsigned long long)1)<<i)) {
            106                 ++cnt;
            107                 x = i/BOARD;
            108                 y = i%BOARD; 
            109                 for(j=0; j<4; j++) {
            110                     next_x = x + dx[j];
            111                     next_y = y + dy[j];
            112                     if(!is_valid(next_x, next_y))
            113                         continue;
            114                     if(is_set(next_x, next_y, cur_state)) {
            115                         next_x += dx[j];
            116                         next_y += dy[j];
            117                         if(!is_valid(next_x, next_y))
            118                             continue;
            119                     }
            120                     next_state = cur_state;
            121                     clear_bit(x, y, next_state);
            122                     set_bit(next_x, next_y, next_state);
            123                     if(!check_hash(second_hash_table, next_state) && second_cur_move<MOVE_MAX/2) {
            124                         if(check_hash(hash_table, next_state)) 
            125                             return 1;
            126                         ++second_tail;
            127                         second_queue[second_tail].move = second_cur_move + 1;
            128                         second_queue[second_tail].state = next_state;
            129                         insert_hash(second_hash_table, &(second_queue[second_tail].state), (second_queue[second_tail].state)%PRIME);
            130                     } 
            131                 }
            132             }
            133         }
            134     }
            135     return 0;
            136 }
            137 
            138 int
            139 main(int argc, char **argv)
            140 {
            141     int i, j, k;
            142     while(scanf("%d %d"&i, &j) != EOF) {
            143         head = second_head = -1;
            144         tail = second_tail = 0;
            145         begin = end = 0;
            146         set_bit(i-1, j-1, begin);
            147         memset(hash_table, 0sizeof(hash_table));
            148         memset(second_hash_table, 0sizeof(second_hash_table));
            149         memset(queue, 0sizeof(queue));
            150         memset(second_queue, 0sizeof(second_queue));
            151         for(k=1; k<4; k++) {
            152             scanf("%d %d"&i, &j);
            153             set_bit(i-1, j-1, begin);
            154         }
            155         for(k=0; k<4; k++) {
            156             scanf("%d %d"&i, &j);
            157             set_bit(i-1, j-1, end);
            158         }
            159         printf("%s\n", bfs()==1 ? "YES" : "NO");
            160     }
            161 }


            posted on 2010-07-05 11:56 simplyzhao 閱讀(180) 評論(0)  編輯 收藏 引用 所屬分類: B_搜索

            導(dǎo)航

            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            女人香蕉久久**毛片精品| 亚洲人AV永久一区二区三区久久 | 亚洲一本综合久久| 国产精品美女久久久久av爽| 国产成人无码精品久久久性色| 久久久久亚洲av无码专区喷水 | 久久精品国产精品国产精品污| 66精品综合久久久久久久| 思思久久好好热精品国产| 国产韩国精品一区二区三区久久| 国内精品久久久久久不卡影院| 亚洲AV无码久久| 久久本道久久综合伊人| 国产精品美女久久久m| 亚洲国产成人精品91久久久 | 人妻精品久久无码区| 久久亚洲2019中文字幕| 色综合久久综精品| 国内精品九九久久久精品| 久久九九久精品国产免费直播| 久久精品国产亚洲欧美| 亚洲欧美伊人久久综合一区二区| 狠狠色综合久久久久尤物| 久久99中文字幕久久| 久久精品aⅴ无码中文字字幕重口| 久久亚洲电影| 婷婷久久综合| 欧美伊人久久大香线蕉综合| 亚洲国产成人精品女人久久久 | 久久久久综合网久久| 久久亚洲欧美国产精品| 亚洲国产精品无码久久久蜜芽 | 亚洲&#228;v永久无码精品天堂久久| AV无码久久久久不卡蜜桃| 国产精品99精品久久免费| 日韩精品久久久久久免费| 久久发布国产伦子伦精品| 久久99国产精品久久99| 91精品国产91久久久久久青草 | 欧美一区二区三区久久综合| 久久婷婷五月综合97色直播|