• <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>
            posts - 33,  comments - 25,  trackbacks - 0
            用位操作+BFS解決.基本思想如下:
            給棋盤每一個狀態賦予一個狀態id,id計算方法是將棋盤與數的二進制表示聯系起來,如題所給的數據:
            bwwb
            bbwb
            bwwb
            bwww
            狀態id為6585,計算方法為1*2^0+0*2^1+1*2^2..1*2^12+0*2^13..=6585(其中b代表1,w代表0)
            在此基礎上進行BFS搜索,首先理解一點,先點(0,0)再點(0,1)與先點(0,1)再點(0,0)對結果不造成任何影響.因此遍歷棋盤的16個位置,將每次點擊后的狀態id利用樹狀結構保存.如:
                                             6585
                                           /   |   \  ...
                                       (0,0) (0,1)  (0,2)
                                        /      |      \  ...
                                     6568     6553     6646
                                  ...............................
            對此樹進行BFS搜索,將id為0(全白)或65535(全黑)的時候則搜索成功,輸出樹的高度,否則輸出"Impossible".
            為了提高搜索效率,采用位運算,如果想將整數的二進制某一位翻轉可采用id^=(1<<x)(x代表要翻轉的位置)
             1 #include "assert.h"
             2 #include <iostream>
             3 #include <queue>
             4 using namespace std;
             5 
             6 const int MAX_STATE = 65536;
             7 const int ALL_WHILE_STATE = 0;
             8 const int ALL_BLACK_STATE = 65535;
             9 const int WIDTH_OF_BOARD = 4;
            10 const int SIZE_OF_BOARD = WIDTH_OF_BOARD * WIDTH_OF_BOARD; // 4 * 4
            11 
            12 int ConvertPieceColorToInt(char color)
            13 {
            14     switch(color)
            15     {
            16     case 'b':
            17         return 1;
            18     case 'w':
            19         return 0;
            20     }
            21 }
            22 
            23 int FlipPiece(int state_id, int position)
            24 {
            25     state_id ^= (1 << position);
            26 
            27     // up
            28     if(position - 4 >= 0)
            29         state_id ^= (1 << (position - 4));
            30     // down
            31     if(position + 4 < SIZE_OF_BOARD)
            32         state_id ^= (1 << (position + 4));
            33     // left
            34     if(position % 4 != 0)
            35         state_id ^= (1 << (position - 1));
            36     // right
            37     if(position % 4 != 3)
            38         state_id ^= (1 << (position + 1));
            39 
            40     return state_id;
            41 }
            42 
            43 int _tmain(int argc, _TCHAR* argv[])
            44 {
            45     int current_state_id = 0;
            46     int state[MAX_STATE];
            47     queue<int> search_queue;
            48 
            49     memset(state, -1sizeof(state));
            50 
            51     char color;
            52 
            53     for(int i = 0; i < SIZE_OF_BOARD; ++i)
            54     {
            55         cin >> color;
            56         current_state_id += ConvertPieceColorToInt(color) << i;
            57     }
            58 
            59     if(current_state_id == ALL_WHILE_STATE
            60         || current_state_id == ALL_BLACK_STATE)
            61     {
            62         cout << "0" << endl;
            63         return 0;
            64     }
            65 
            66     state[current_state_id] = 0;
            67     search_queue.push(current_state_id);
            68 
            69     int next_state_id;
            70 
            71     while(!search_queue.empty())
            72     {
            73         current_state_id = search_queue.front();
            74         search_queue.pop();
            75 
            76         for(int i = 0; i < SIZE_OF_BOARD; ++i)
            77         {
            78             next_state_id = FlipPiece(current_state_id, i);
            79             if(next_state_id == ALL_WHILE_STATE
            80                 || next_state_id == ALL_BLACK_STATE)
            81             {
            82                 cout << state[current_state_id] + 1 << endl;
            83                 return 0;
            84             }
            85             assert(next_state_id < MAX_STATE);
            86             if(state[next_state_id] == -1 /* not visited */)
            87             {
            88                 state[next_state_id] = state[current_state_id] + 1;
            89                 search_queue.push(next_state_id);
            90             }
            91         }
            92     }
            93 
            94     cout << "Impossible" << endl;
            95     return 0;
            96 }
            97 
            98 

            posted on 2009-03-21 10:30 肖羽思 閱讀(5069) 評論(8)  編輯 收藏 引用 所屬分類: POJ

            FeedBack:
            # re: POJ 1753 解題報告
            2009-10-04 10:36 | pcfeng502
            狀態id為6585,計算方法為1*2^0+0*2^1+1*2^2..1*2^12+0*2^13..=6585(其中b代表1,w代表0)

            按照樓主給的圖(狀態),這里是
            1*2^0+0*2^1+0*2^2..1*2^12+1*2^13..=6585(其中b代表1,w代表0)


            P.S.比較欣賞樓主這種用隊列實現的清晰的寫法
              回復  更多評論
              
            # re: POJ 1753 解題報告
            2010-07-06 17:59 | Tanky Woo
            看了你的數據,學習了。
            不過,那個斷言你可以去掉,我測試了
            沒去掉:
            Memory: 516K Time: 63MS
            Language: C++ Result: Accepted

            去掉后:
            Memory: 504K Time: 16MS
            Language: C++ Result: Accepted
              回復  更多評論
              
            # re: POJ 1753 解題報告
            2010-11-28 20:06 | talenth1
            其實,把每個狀態看成一個圖的點,用位運算建立一個圖,用spfa瞬間秒殺。。。但是比起裸寬搜還是慢點。。。。
            5616K 797MS
            空間比較多。。。。。  回復  更多評論
              
            # re: POJ 1753 解題報告
            2010-11-29 10:49 | 肖羽思
            @Tanky Woo
            寫斷言是一種習慣......  回復  更多評論
              
            # re: POJ 1753 解題報告
            2010-11-29 10:49 | 肖羽思
            @pcfeng502

            謝謝~~你能有所收獲是我最欣慰的事情~
              回復  更多評論
              
            # re: POJ 1753 解題報告
            2010-11-29 10:50 | 肖羽思
            @talenth1

            謝謝提供新思路~~不過好像慢了蠻多~~不能說是瞬間秒殺了...:)  回復  更多評論
              
            # re: POJ 1753 解題報告
            2011-04-28 16:14 | yangyh
            這算法好像有冗余吧

            FlipPiece(6585,0)=6570之后就不用FlipPiece(6570,0)了吧  回復  更多評論
              
            # re: POJ 1753 解題報告
            2012-05-09 21:53 | hacker003
            LZ的位運算計算法果然比我的普通方法快很多啊!!!
            感謝分享?。?!  回復  更多評論
              
            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            精品久久久久久国产三级| 女人高潮久久久叫人喷水| 亚洲国产精品久久电影欧美| 99久久这里只精品国产免费| 久久精品国产亚洲AV香蕉| A级毛片无码久久精品免费| 国内精品久久国产大陆| 思思久久99热只有频精品66| 久久久久久久波多野结衣高潮| 亚洲精品国精品久久99热一| 亚洲一本综合久久| 久久精品aⅴ无码中文字字幕不卡| 亚洲一区二区三区日本久久九| 欧美久久天天综合香蕉伊| 久久久高清免费视频| 91久久精品国产成人久久| 久久久久无码精品国产| 精品国产日韩久久亚洲| 久久国产精品波多野结衣AV| 97r久久精品国产99国产精| 欧美日韩精品久久久久| 日韩精品久久久久久久电影蜜臀| 久久国产香蕉视频| 久久国产精品99久久久久久老狼| 亚洲午夜精品久久久久久app| 韩国三级中文字幕hd久久精品| 久久不见久久见免费视频7| 久久久久噜噜噜亚洲熟女综合| 久久性生大片免费观看性| 久久久久久A亚洲欧洲AV冫| 国内精品久久久久久不卡影院| 久久国产精品99久久久久久老狼| 精品人妻伦九区久久AAA片69| 免费久久人人爽人人爽av| 久久亚洲AV成人无码电影| 2022年国产精品久久久久| 久久久久亚洲精品天堂久久久久久| 久久久久国产精品嫩草影院 | www亚洲欲色成人久久精品| 美女久久久久久| 久久国产精品一区|