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

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            日韩电影久久久被窝网| 久久这里只有精品首页| 久久精品无码一区二区无码| 亚洲日本va中文字幕久久| 激情伊人五月天久久综合| 国内精品久久久久久久亚洲| 久久国产亚洲精品| 久久久无码精品亚洲日韩按摩| 国产精品女同久久久久电影院| 国产日韩欧美久久| 波多野结衣久久一区二区 | 精品国产乱码久久久久久呢| 久久久久亚洲AV无码网站| 久久国产香蕉视频| 人妻精品久久无码区| 热综合一本伊人久久精品| 久久综合香蕉国产蜜臀AV| 色综合久久88色综合天天 | 国产韩国精品一区二区三区久久| 欧美麻豆久久久久久中文| 久久综合久久综合九色| 日韩AV无码久久一区二区| 亚洲精品成人网久久久久久| 久久99热国产这有精品| 99久久夜色精品国产网站| 久久精品国产黑森林| 久久久久人妻一区二区三区vr | 亚洲国产成人精品久久久国产成人一区二区三区综 | 无码8090精品久久一区| 亚洲国产成人久久精品动漫| 伊人久久大香线蕉亚洲五月天| 精品国产91久久久久久久a| 国产精品一区二区久久| 久久婷婷国产综合精品| 亚洲国产精品无码久久久蜜芽| 伊人久久大香线蕉无码麻豆| 人妻少妇精品久久| 香蕉久久夜色精品国产2020| 性高湖久久久久久久久AAAAA| 欧美国产成人久久精品| 久久露脸国产精品|