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

            USACO Section 2.4 The Tamworth Two

            The Tamworth Two

            BIO '98 - Richard Forster

            A pair of cows is loose somewhere in the forest. Farmer John is lending his expertise to their capture. Your task is to model their behavior.

            The chase takes place on a 10 by 10 planar grid. Squares can be empty or they can contain:

            • an obstacle,
            • the cows (who always travel together), or
            • Farmer John.

            The cows and Farmer John can occupy the same square (when they `meet') but neither the cows nor Farmer John can share a square with an obstacle.

            Each square is
            represented
            as follows:

            • . Empty square
            • * Obstacle
            • C Cows
            • F Farmer
            Here is a sample grid:
                        *...*.....
                        ......*...
                        ...*...*..
                        ..........
                        ...*.F....
                        *.....*...
                        ...*......
                        ..C......*
                        ...*.*....
                        .*.*......
                        

            The cows wander around the grid in a fixed way. Each minute, they either move forward or rotate. Normally, they move one square in the direction they are facing. If there is an obstacle in the way or they would leave the board by walking `forward', then they spend the entire minute rotating 90 degrees clockwise.

            Farmer John, wise in the ways of cows, moves in exactly the same way.

            The farmer and the cows can be considered to move simultaneously during each minute. If the farmer and the cows pass each other while moving, they are not considered to have met. The chase ends when Farmer John and the cows occupy the same square at the end of a minute.

            Read a ten-line grid that represents the initial state of the cows, Farmer John, and obstacles. Each of the ten lines contains exactly ten characters using the coding above. There is guaranteed to be only one farmer and one pair of cows. The cows and Farmer John will not initially be on the same square.

            Calculate the number of minutes until the cows and Farmer John meet. Assume both the cows and farmer begin the simulation facing in the `north' direction. Print 0 if they will never meet.

            PROGRAM NAME: ttwo

            INPUT FORMAT

            Lines 1-10: Ten lines of ten characters each, as explained above

            SAMPLE INPUT (file ttwo.in)

            *...*.....
            ......*...
            ...*...*..
            ..........
            ...*.F....
            *.....*...
            ...*......
            ..C......*
            ...*.*....
            .*.*......
            

            OUTPUT FORMAT

            A single line with the integer number of minutes until Farmer John and the cows meet. Print 0 if they will never meet.

            SAMPLE OUTPUT (file ttwo.out)

            49
            
            Analysis
            A simulating problem. These problems aims to replay actions by programs. Moreover, the total number of situations is 160000, which is used to make sure whether these two will never meet.
            Code
            /*
            ID: braytay1
            PROG: ttwo
            LANG: C++
            */

            #include 
            <iostream>
            #include 
            <fstream>
            using namespace std;

            char map[10][10];
            struct cows{
                
            int x;
                
            int y;
                
            int face;
            }
            cow,farmer;
            bool in(int x,int y){
                
            if (x<0||x>=10return false;
                
            if (y<0||y>=10return false;
                
            else return true;
            }

            int main(){
                ifstream fin(
            "ttwo.in");
                ofstream fout(
            "ttwo.out");
                
            for (int i=0;i<10;i++){
                    
            for (int j=0;j<10;j++){
                        fin
            >>map[i][j];
                    }

                }

                
            int time=0,met=0,x,y;
                
            for (int i=0;i<10;i++){
                    
            for (int j=0;j<10;j++){
                        
            if (map[i][j]=='C'{
                            cow.x
            =i;
                            cow.y
            =j;
                            cow.face
            =1;
                            map[i][j]
            ='.';
                        }

                        
            if (map[i][j]=='F'{
                            farmer.x
            =i;
                            farmer.y
            =j;
                            farmer.face
            =1;
                            map[i][j]
            ='.';
                        }

                    }

                }

                
            for (;time<=160000;time++){
                    
            if (cow.x==farmer.x&&cow.y==farmer.y){
                        met
            =1;
                        fout
            <<time<<endl;
                        
            return 0;
                    }

                    x
            =cow.x;y=cow.y;
                    
            switch(cow.face){
                        
            case 1:if(map[x-1][y]=='.'&&in(x-1,y)){cow.x--;break;}
                               
            else {
                                   cow.face
            =(cow.face+1)%4;
                                   
            break;
                               }

                        
            case 2:if(map[x][y+1]=='.'&&in(x,y+1)){cow.y++;break;}
                               
            else {
                                   cow.face
            =(cow.face+1)%4;
                                   
            break;
                               }

                        
            case 3:if(map[x+1][y]=='.'&&in(x+1,y)){cow.x++;break;}
                               
            else {
                                   cow.face
            =(cow.face+1)%4;
                                   
            break;
                               }

                        
            case 0:if(map[x][y-1]=='.'&&in(x,y-1)){cow.y--;break;}
                               
            else {
                                   cow.face
            =(cow.face+1)%4;
                                   
            break;
                               }

                    }

                    x
            =farmer.x;y=farmer.y;
                    
            switch(farmer.face){
                        
            case 1:if(map[x-1][y]=='.'&&in(x-1,y)){farmer.x--;break;}
                               
            else {
                                   farmer.face
            =(farmer.face+1)%4;
                                   
            break;
                               }

                        
            case 2:if(map[x][y+1]=='.'&&in(x,y+1)){farmer.y++;break;}
                               
            else {
                                   farmer.face
            =(farmer.face+1)%4;
                                   
            break;
                               }

                        
            case 3:if(map[x+1][y]=='.'&&in(x+1,y)){farmer.x++;break;}
                               
            else {
                                   farmer.face
            =(farmer.face+1)%4;
                                   
            break;
                               }

                        
            case 0:if(map[x][y-1]=='.'&&in(x,y-1)){farmer.y--;break;}
                               
            else {
                                   farmer.face
            =(farmer.face+1)%4;
                                   
            break;
                               }

                    }

                }

                
            if (met==0) fout<<0<<endl;
                
            return 0;
            }

            posted on 2008-08-13 20:59 幻浪天空領主 閱讀(240) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲国产精品久久久久网站| 久久久久av无码免费网| 久久精品国产亚洲精品2020 | 麻豆av久久av盛宴av| 777米奇久久最新地址| 亚洲v国产v天堂a无码久久| 久久精品无码一区二区无码| 精品国产热久久久福利| 国产精品欧美久久久天天影视 | 亚洲欧美国产精品专区久久| 久久精品国产只有精品2020| 无码伊人66久久大杳蕉网站谷歌| 亚洲精品午夜国产va久久| 国产高潮国产高潮久久久91 | 免费一级欧美大片久久网 | 久久综合伊人77777| 97久久超碰成人精品网站| 国产精品久久久久蜜芽| 久久精品中文字幕第23页| 久久精品无码专区免费| 精品国际久久久久999波多野| 久久久久99精品成人片直播| 合区精品久久久中文字幕一区| 久久96国产精品久久久| 国产情侣久久久久aⅴ免费| 久久人人爽人人爽人人片av麻烦 | 国产美女久久久| 99久久婷婷国产综合亚洲| 久久久一本精品99久久精品88| 久久妇女高潮几次MBA| 噜噜噜色噜噜噜久久| 久久久久久免费视频| 伊人精品久久久久7777| 麻豆av久久av盛宴av| 精产国品久久一二三产区区别| 久久亚洲2019中文字幕| 国产精品免费看久久久香蕉| 91精品国产综合久久香蕉 | 久久久久国产亚洲AV麻豆| 久久久久久亚洲精品无码| 欧美午夜A∨大片久久 |