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

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            色婷婷久久综合中文久久蜜桃av| 国内精品久久久久久久久电影网 | 91久久婷婷国产综合精品青草| 久久精品国产亚洲AV香蕉| 成人免费网站久久久| 国内精品久久久久久久coent| 狠狠色丁香久久婷婷综合_中 | 精品无码久久久久久久动漫| 污污内射久久一区二区欧美日韩 | 精品无码久久久久久久久久| 亚洲欧美日韩精品久久亚洲区| 亚洲国产另类久久久精品小说 | 久久久91精品国产一区二区三区| 麻豆国内精品久久久久久| 亚洲狠狠婷婷综合久久蜜芽| 久久久中文字幕| 亚洲AV日韩精品久久久久久| 精品久久久久久| 天天爽天天狠久久久综合麻豆| 热综合一本伊人久久精品| 久久线看观看精品香蕉国产| 伊人色综合久久天天人手人婷| 久久久久久毛片免费看| 国产成人久久精品一区二区三区| 国产精品久久久香蕉| 女同久久| 欧美午夜A∨大片久久 | 久久99热这里只频精品6| 青青青国产精品国产精品久久久久| 国产精品久久久久a影院| 精品国产综合区久久久久久| 久久精品国产亚洲AV香蕉| 久久99久久99精品免视看动漫| 性做久久久久久久久久久| 久久精品亚洲男人的天堂| 亚洲国产精品婷婷久久| 97久久精品国产精品青草| 狠狠色丁香久久综合婷婷| 久久96国产精品久久久| 国产精品久久久久影院嫩草| www久久久天天com|