• <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 3.3 Home on the Range

            Home on the Range

            Farmer John grazes his cows on a large, square field N (2 <= N <= 250) miles on a side (because, for some reason, his cows will only graze on precisely square land segments). Regrettably, the cows have ravaged some of the land (always in 1 mile square increments). FJ needs to map the remaining squares (at least 2x2 on a side) on which his cows can graze (in these larger squares, no 1x1 mile segments are ravaged).

            Your task is to count up all the various square grazing areas within the supplied dataset and report the number of square grazing areas (of sizes >= 2x2) remaining. Of course, grazing areas may overlap for purposes of this report.

            PROGRAM NAME: range

            INPUT FORMAT

            Line 1: N, the number of miles on each side of the field.
            Line 2..N+1: N characters with no spaces. 0 represents "ravaged for that block; 1 represents "ready to eat".

            SAMPLE INPUT (file range.in)

            6
            101111
            001111
            111111
            001111
            101101
            111001
            

            OUTPUT FORMAT

            Potentially several lines with the size of the square and the number of such squares that exist. Order them in ascending order from smallest to largest size.

            SAMPLE OUTPUT (file range.out)

            2 10
            3 4
            4 1  
            Analysis

            It is really a dynamic problem rather than a geometry problem, which is appeared at first time. However, it is easy to contribute a dynamic function later to replace older method.
            Initially, map[i][j], established by initial input, stands for the minimum length of a square, which its left-top point is (i,j). And, for the nearby points (i+1,j), (i,j+1) and (i+1,j+1),if all avaliable, map[i][j] can be expanded by these three points since map[i][j] is truly depended on these three values.
            What's more, considering the avaliable one for (i,j) is the minimum of these, then map[i][j]=min{map[i+1][j],map[i][j+1],map[i+1][j+1]}+1.
            Additionally, only is the function hold when all of the four points is avaliable!

            Code

            /*
            ID:braytay1
            PROG:range
            LANG:C++
            */

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

            int n;
            int g[250][250],sum[251];
            int min(int a,int b,int c){
                
            if (a>b) return (b>c)?c:b;
                
            else return (a>c)?c:a;
            }

            int main(){
                ifstream fin(
            "range.in");
                ofstream fout(
            "range.out");
                fin
            >>n;
                
            string tmp;
                memset(g,
            0,sizeof g);
                
            for (int i=0;i<n;i++){
                    fin
            >>tmp;
                    
            for (int j=0;j<n;j++){
                        g[i][j]
            =(tmp[j]=='1')?1:0;
                    }

                    tmp.clear();
                }
                
                
            for (int i=n-2;i>=0;i--)
                    
            for (int j=n-2;j>=0;j--){
                        
            if (g[i][j]&&g[i+1][j]&&g[i][j+1]&&g[i+1][j+1])
                            g[i][j]
            =min(g[i+1][j],g[i][j+1],g[i+1][j+1])+1;
                    }

                memset(sum,
            0,sizeof sum);
                
            for (int i=0;i<n-1;i++)
                    
            for (int j=0;j<n-1;j++){
                        
            int s;
                        s
            =g[i][j];
                        sum[s]
            ++;
                    }
             
                
            for (int i=2;i<=n;i++){
                    
            for (int j=i+1;j<=n;j++){
                        sum[i]
            +=sum[j];
                    }

                }

                
            for (int i=2;i<=n;i++)
                    
            if (sum[i]) fout<<i<<" "<<sum[i]<<endl;
                
            return 0;
            }


            posted on 2008-08-28 23:43 幻浪天空領主 閱讀(255) 評論(0)  編輯 收藏 引用 所屬分類: USACO

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

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            国产精品gz久久久| 蜜桃麻豆WWW久久囤产精品| 日韩AV毛片精品久久久| 日韩av无码久久精品免费| 97热久久免费频精品99| 久久久受www免费人成| 婷婷久久香蕉五月综合加勒比| 青青青青久久精品国产| 国产精品成人久久久| 91秦先生久久久久久久| 亚洲精品乱码久久久久久中文字幕| 久久久久国产一级毛片高清版| 99精品国产99久久久久久97| 久久国产精品波多野结衣AV| 久久偷看各类wc女厕嘘嘘| 一本久久综合亚洲鲁鲁五月天| 伊人久久免费视频| av国内精品久久久久影院| 久久久久久久精品成人热色戒| 国产一区二区精品久久岳| 东京热TOKYO综合久久精品| 久久人妻少妇嫩草AV蜜桃| 久久亚洲国产精品五月天婷| 一本伊大人香蕉久久网手机| 久久精品成人免费看| 久久国产高潮流白浆免费观看| 区久久AAA片69亚洲| 亚洲欧美久久久久9999| 人妻中文久久久久| 久久久久亚洲AV无码去区首| 精品久久综合1区2区3区激情| 91超碰碰碰碰久久久久久综合| 精品久久久久久久| 波多野结衣中文字幕久久| www久久久天天com| 色综合久久天天综合| 久久综合狠狠色综合伊人| 天天综合久久久网| 国产激情久久久久影院老熟女免费| 国产精品久久久久久久午夜片| 久久久精品波多野结衣|