• <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 幻浪天空領主 閱讀(239) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            精品伊人久久大线蕉色首页| 国产69精品久久久久99尤物| 精品久久久久久| 久久夜色精品国产噜噜麻豆| 欧美精品乱码99久久蜜桃| 久久久久国产一区二区三区| 伊人久久综在合线亚洲2019 | 久久精品国产第一区二区三区| 亚洲精品成人网久久久久久| 久久天天躁狠狠躁夜夜96流白浆| 伊人精品久久久久7777| 日韩av无码久久精品免费| 久久综合亚洲欧美成人| 久久综合狠狠色综合伊人| 99久久99久久精品国产片| 日本三级久久网| 国产一区二区三区久久精品| 久久精品无码专区免费青青| 天天久久狠狠色综合| 久久精品一区二区国产| 久久婷婷五月综合97色直播| 亚洲精品蜜桃久久久久久| 久久亚洲高清综合| 久久综合亚洲色一区二区三区| 久久亚洲sm情趣捆绑调教| 久久综合亚洲色HEZYO社区| 亚洲AV无码1区2区久久 | 97精品国产97久久久久久免费 | 久久国产香蕉一区精品| 亚洲AV无码久久| 亚洲精品无码久久一线| 2021国内久久精品| 国产欧美久久久精品影院| 99久久精品日本一区二区免费| 狠色狠色狠狠色综合久久| 天堂无码久久综合东京热| 四虎国产精品免费久久久| 精品久久综合1区2区3区激情| 亚洲欧洲中文日韩久久AV乱码| 亚洲国产精品无码久久青草| 午夜精品久久久久成人|