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

            Overfencing

            Kolstad and Schrijvers

            Farmer John went crazy and created a huge maze of fences out in a field. Happily, he left out two fence segments on the edges, and thus created two "exits" for the maze. Even more happily, the maze he created by this overfencing experience is a `perfect' maze: you can find a way out of the maze from any point inside it.

            Given W (1 <= W <= 38), the width of the maze; H (1 <= H <= 100), the height of the maze; 2*H+1 lines with width 2*W+1 characters that represent the maze in a format like that shown later - then calculate the number of steps required to exit the maze from the `worst' point in the maze (the point that is `farther' from either exit even when walking optimally to the closest exit). Of course, cows walk only parallel or perpendicular to the x-y axes; they do not walk on a diagonal. Each move to a new square counts as a single unit of distance (including the move "out" of the maze.

            Here's what one particular W=5, H=3 maze looks like:

            +-+-+-+-+-+
            |         |
            +-+ +-+ + +
            |     | | |
            + +-+-+ + +
            | |     |
            +-+ +-+-+-+
            

            Fenceposts appear only in odd numbered rows and and odd numbered columns (as in the example). The format should be obvious and self explanatory. Each maze has exactly two blank walls on the outside for exiting.

            PROGRAM NAME: maze1

            INPUT FORMAT

            Line 1: W and H, space separated
            Lines 2 through 2*H+2: 2*W+1 characters that represent the maze

            SAMPLE INPUT (file maze1.in)

            5 3
                +-+-+-+-+-+
                |         |
                +-+ +-+ + +
                |     | | |
                + +-+-+ + +
                | |     |
                +-+ +-+-+-+
                

            OUTPUT FORMAT

            A single integer on a single output line. The integer specifies the minimal number of steps that guarantee a cow can exit the maze from any possible point inside the maze.

            SAMPLE OUTPUT (file maze1.out)

            9
                
            The lower left-hand corner is *nine* steps from the closest exit.

            Analysis

            We can solve this with a standard flood fill, using a queue to implement breadth first search. It is convenient to leave the maze in its ASCII format and just look at it as a bunch of characters, with non-space characters being walls.


            Code
            /*
            ID: braytay1
            PROG: maze1
            LANG: C++
            */

            #include 
            <stdio.h>
            #include 
            <stdlib.h>
            #include 
            <string.h>
            #include 
            <assert.h>
            #include 
            <algorithm>
            #include 
            <queue>
            using namespace std;
            queue
            <int> qq;
            int W,H;
            char map[202][80];
            int tracy[202][80][2];
            int x1=-1,y1=-1,x2=-1,y2=-1;
            bool isIn(int x,int y){
                
            if (x<=0||x>=2*H||y<=0||y>=2*W) return false;
                
            else return true;
            }

            void BFS(int tra){
                
            int col,row,s;
                
            while (!qq.empty()){
                    col
            =qq.front();
                    qq.pop();
                    row
            =qq.front();
                    qq.pop();
                    s
            =qq.front();
                    qq.pop();
                    
            if (tracy[col][row][tra]>0continue;
                    tracy[col][row][tra]
            =s;
                    
            if (map[col-1][row]!='-'&&isIn(col-2,row)) {qq.push(col-2);qq.push(row);qq.push(s+1);}
                    
            if (map[col+1][row]!='-'&&isIn(col+2,row)) {qq.push(col+2);qq.push(row);qq.push(s+1);}
                    
            if (map[col][row-1]!='|'&&isIn(col,row-2)) {qq.push(col);qq.push(row-2);qq.push(s+1);}
                    
            if (map[col][row+1]!='|'&&isIn(col,row+2)) {qq.push(col);qq.push(row+2);qq.push(s+1);}
                }

            }

            int max(int a[202][80][2],int tra,int h,int w){
                
            int maximum=-1;
                
            for (int i=0;i<h;i++){
                    
            for (int j=0;j<w;j++){
                        
            if (maximum<a[i][j][tra]) maximum=a[i][j][tra];
                    }

                }

                
            return maximum;
            }


            int main(){
                
            //Initialize
                FILE *fin, *fout;
                fin 
            = fopen("maze1.in""r");
                fout 
            = fopen("maze1.out""w");
                assert(fin 
            != NULL && fout != NULL);
                fscanf(fin,
            "%d %d\n",&W,&H);
                
            for (int i=0;i<=2*H;i++){
                    fgets(map[i], 
            sizeof(map[i]), fin);
                }

                memset(tracy,
            -1,sizeof(tracy));
                
            //edge search
                for (int i=0;i<=2*W;i++){
                    
            if (map[0][i]!='+'&&map[0][i]!='-'{
                        
            if (x1==-1&&y1==-1{x1=1;y1=i;}
                        
            else {x2=1;y2=i;}
                    }

                    
            if (map[2*H][i]!='+'&&map[2*H][i]!='-'{
                        
            if (x1==-1&&y1==-1{x1=2*H-1;y1=i;}
                        
            else {x2=2*H-1;y2=i;}
                    }

                }

                
            for (int i=0;i<=2*H;i++){
                    
            if (map[i][0]!='+'&&map[i][0]!='|'{
                        
            if (x1==-1&&y1==-1{x1=i;y1=1;}
                        
            else {x2=i;y2=1;}
                    }

                    
            if (map[i][2*W]!='+'&&map[i][2*W]!='|'{
                        
            if (x1==-1&&y1==-1{x1=i;y1=2*W-1;}
                        
            else {x2=i;y2=2*W-1;}
                    }

                }

                qq.push(x1);qq.push(y1);qq.push(
            1);
                BFS(
            0);
                qq.push(x2);qq.push(y2);qq.push(
            1);
                BFS(
            1);
                
            for (int i=0;i<=2*H;i++){
                    
            for (int j=0;j<=2*W;j++){
                        
            int a1,a2;
                        a1
            =tracy[i][j][0];
                        a2
            =tracy[i][j][1];
                        tracy[i][j][
            0]=(a1<a2)?a1:a2;
                    }

                }

                
            int res;
                res
            =max(tracy,0,2*H+1,2*W+1);
                
            //Output
                fprintf(fout, "%d\n", res);
                
            return 0;
            }

            posted on 2008-08-15 16:55 幻浪天空領(lǐng)主 閱讀(148) 評論(0)  編輯 收藏 引用 所屬分類: USACO

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

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            www.久久热| 99久久国产主播综合精品| 亚洲国产精品婷婷久久| 国产精品成人精品久久久| 久久亚洲高清综合| 亚洲午夜久久久久妓女影院| 欧美精品国产综合久久| 久久亚洲AV成人出白浆无码国产| 久久精品蜜芽亚洲国产AV| 狠狠人妻久久久久久综合蜜桃| 综合久久精品色| 一级女性全黄久久生活片免费 | 人妻精品久久无码专区精东影业| 欧美亚洲国产精品久久蜜芽 | 嫩草影院久久99| 久久久久久亚洲AV无码专区| 亚洲午夜久久久久妓女影院| 亚洲国产成人精品91久久久 | 久久婷婷国产综合精品| 久久这里只有精品视频99| 久久婷婷综合中文字幕| 久久国产一区二区| 国产亚洲美女精品久久久久狼| 国产精品99久久久精品无码| 久久精品中文无码资源站| 国产精品一区二区久久精品涩爱| 无码国内精品久久人妻麻豆按摩| 国产日韩欧美久久| 久久久久久精品久久久久| 久久天天躁狠狠躁夜夜躁2014| 亚洲成色www久久网站夜月| 久久99精品国产自在现线小黄鸭| 国产人久久人人人人爽| 精品久久人人妻人人做精品| 一级a性色生活片久久无| 久久夜色精品国产噜噜亚洲AV| 久久精品成人免费看| 性高湖久久久久久久久| 久久久久国产亚洲AV麻豆| 99久久精品日本一区二区免费| 久久久久久噜噜精品免费直播 |