• <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>

            Why so serious? --[NKU]schindlerlee

            2010年1月31日星期日.ural1060-pku1753 枚舉狀態

            2010年1月31日星期日.ural1060-pku1753
            Neerc2000中的一題。

            題目要求:

            給出一個4×4的棋盤的黑白狀態,求最少需要多少次翻轉(每次翻轉會改變當前格和周圍四個格的
            狀態),使棋盤變成全黑或者全白。

            貌似是這套題中最水的一題,分析一下復雜度,發現即使完全枚舉狀態,復雜度也是可以接受的,
            然后就枚舉吧。

            我的存儲方法是用一個int型表示棋盤狀態,黑1白0,將四行按順序連起來,寫成一個16位整數。


             1 
             2 const int inf = 0x7fffffff;
             3 #define bin(x) (1 <<(x))
             4 int mask = bin(16- 1;
             5 int addr(const int &x,const int &y)
             6 return x * 4 + y; }
             7 int grid;
             8 //http://www.shnenglu.com/schindlerlee
             9 bool flip(int press)
            10 {
            11   int g = grid,i;
            12   for (i = 0;i < 16;i++) {
            13       if(press & bin(i)) {
            14           g ^= bin(i);
            15           g ^= bin(i + 4);
            16           g ^= bin(i - 4);
            17           if (i != 3 && i!= 7 && i != 11 && i!= 15) { g ^= bin(i+1); }
            18           if (i != 0 && i!= 4 && i != 8 && i!= 12)  { g ^= bin(i-1); }
            19       }
            20   }
            21   g &= mask;
            22   return (g == 0|| (g == mask);
            23 }
            24 
            25 int count(int x)
            26 {
            27   int res = 0;
            28   while(x > 0) {
            29       res += x & 1;
            30       x >>= 1;
            31   }
            32   return res;
            33 }
            34 
            35 void ckmin(int & res,int x) { if(x < res) res = x; }
            36 int main()
            37 {
            38   char s[16];
            39   int i,j;
            40   for (i = 0;i < 4;i++) {
            41       scanf("%s\n",s);
            42       for (j = 0;j < 4;j++) {
            43           if(s[j] == 'b') {
            44               grid |= bin(addr(i,j));
            45           }
            46       }
            47   }
            48 
            49   int res = inf;
            50   for (i = 0;i <= mask;i++) {
            51       if (flip(i)) {
            52           //printf("i=%d\n",i);
            53           ckmin(res,count(i));
            54       }
            55   }
            56   if(res == inf) {
            57       printf("Impossible\n");
            58   }else {
            59       printf("%d\n",res);
            60   }
            61   return 0;
            62 }
            63 

            posted on 2010-01-31 23:31 schindlerlee 閱讀(1025) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            久久99热这里只有精品66| 国产精品久久久久aaaa| 国产欧美久久久精品影院| 久久久久久久97| 日本免费久久久久久久网站| 久久久久亚洲精品无码网址| 色婷婷久久综合中文久久蜜桃av| 色综合久久天天综合| 久久久精品视频免费观看| 久久99精品久久久久久久不卡| 久久人人爽人人爽AV片| 亚洲精品乱码久久久久久蜜桃不卡 | 一本一道久久a久久精品综合| 久久99精品久久久久婷婷| 亚洲?V乱码久久精品蜜桃| 久久99国产精品二区不卡| 久久精品国产亚洲av麻豆蜜芽| 国内精品久久九九国产精品| 亚洲AV无码久久精品色欲| 无码人妻久久一区二区三区蜜桃 | 午夜精品久久影院蜜桃| 精品永久久福利一区二区| 中文字幕精品无码久久久久久3D日动漫 | 久久这里的只有是精品23| 亚洲国产成人久久精品动漫| 亚洲成色WWW久久网站| 亚洲国产日韩欧美综合久久| 国产精品99久久久久久www| 国产精品99久久免费观看| 天堂久久天堂AV色综合| 久久久久久综合网天天| 久久亚洲精品无码播放| 国产精品永久久久久久久久久| 精品久久久久香蕉网| 无码专区久久综合久中文字幕 | 久久精品午夜一区二区福利| 亚洲AV日韩AV天堂久久| 新狼窝色AV性久久久久久| 日韩乱码人妻无码中文字幕久久| 无码精品久久久久久人妻中字| 一本久久a久久精品vr综合|