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

            Ural 1060 Flip Game

            C++ Accepted
            0.031 197 KB


            1060. Flip Game

            Time Limit: 2.0 second
            Memory Limit: 16 MB
            Flip game is played on a rectangular 4×4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:
            1. Choose any one of the 16 pieces.
            2. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).
            Problem illustration
            Consider the following position as an example:
            bwbw
                        wwww
                        bbwb
                        bwwb
                        
            Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:
            bwbw
                        bwww
                        wwwb
                        wwwb
                        
            The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.

            Input

            The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.

            Output

            Write to the output a single integer number — the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).

            Sample

            input output
            bwbw
                        wwww
                        bbwb
                        bwwb
                        
            Impossible
                        
            Problem Source: 2000-2001 ACM Northeastern European Regional Programming Contest

            wa了幾次
            原因:1是cnt只增沒減
                         2是search的推出條件寫成if(m==16){ ……},這種情況下對于只改變最后一個即可得情況沒有判定。改成m>16

            #include<iostream>
            using namespace std;
            bool status[6][6]={0};
            const int MAX=0x7fffffff;
            int cnt=0,cntMin=MAX;        

            bool check()
            {
                
            bool f=status[1][1];
                
            int i,j;
                
            for(i=1; i<=4; i++)
                
            for(j=1; j<=4; j++)
                   
            if(f!=status[i][j])return false;
                
                
            return true;
            }

            void turn(int i, int j)
            {
                 status[i][j]
            =!status[i][j];
                 status[i
            -1][j]=!status[i-1][j];
                 status[i
            +1][j]=!status[i+1][j];
                 status[i][j
            -1]=!status[i][j-1];
                 status[i][j
            +1]=!status[i][j+1];
            }

            void input()
            {
                 
            char ch;
                 
            for(int i=1; i<=4; i++)
                 
            for(int j=1; j<=4; j++)
                 {
                         cin
            >>ch;
                         status[i][j]
            =(ch=='b' ? 0 : 1 );
                 }


            void search(int m)
            {
                    
            if(m>16){
                             
            if( check() && (cnt<cntMin) )cntMin=cnt;     
                             
            return ;
                    }
                    
            int i=(m+3)/4
                    
            int j=m-4*(i-1);
                    
                    turn(i,j); cnt
            ++;
                    search(m
            +1);
                    
                    turn(i,j);cnt
            --;
                    search(m
            +1);   
            }

            int main()
            {
                input();   
                search(
            1);
                
            if(cntMin==MAX)cout<<"Impossible"<<endl;
                
            else cout<<cntMin<<endl;
                system(
            "pause");
                
            return 0;
            }

            posted on 2010-07-31 21:44 田兵 閱讀(311) 評論(0)  編輯 收藏 引用 所屬分類: URAL

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

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            97久久国产露脸精品国产| 波多野结衣久久一区二区| 18岁日韩内射颜射午夜久久成人| 久久久久久国产精品美女 | 久久久久亚洲av综合波多野结衣| 久久妇女高潮几次MBA| 国色天香久久久久久久小说| 国产精品久久久久久搜索| 久久精品国产一区二区三区不卡| 久久伊人精品一区二区三区| 久久精品国产99国产精品澳门| 中文字幕精品久久| 亚洲AV无码1区2区久久| 久久久中文字幕日本| 色综合久久88色综合天天| 久久精品国产欧美日韩99热| 99久久精品费精品国产| 天天爽天天狠久久久综合麻豆| 亚洲国产精久久久久久久| 无码人妻少妇久久中文字幕蜜桃| 久久国产精品99精品国产987| 精品久久久无码21p发布| 九九热久久免费视频| 九九久久精品国产| 国产精品久久亚洲不卡动漫| 久久久久久久久久久久久久| 久久精品成人影院| 精品久久久久久无码中文野结衣 | 久久九九精品99国产精品| 四虎国产精品免费久久| 人人狠狠综合88综合久久| 国内精品久久九九国产精品| 亚洲va久久久噜噜噜久久| 久久无码AV一区二区三区| 亚洲另类欧美综合久久图片区| 青青热久久国产久精品| 久久精品免费网站网| 久久久久人妻一区精品| 久久久久无码精品| 久久国产乱子伦免费精品| 久久精品卫校国产小美女|