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

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            曰曰摸天天摸人人看久久久| 精品国产乱码久久久久久1区2区 | 久久99亚洲综合精品首页| 久久久久亚洲AV片无码下载蜜桃| 久久狠狠一本精品综合网| 久久久久国色AV免费观看| 久久精品国产男包| 亚洲AV日韩AV永久无码久久| 亚洲精品乱码久久久久久自慰| 久久精品九九亚洲精品| 久久久久97国产精华液好用吗| 亚洲精品无码久久久影院相关影片 | 久久久久人妻一区精品| 91麻豆国产精品91久久久| 久久99精品久久久久久久不卡 | 久久综合日本熟妇| 久久无码av三级| 奇米综合四色77777久久| 一本色综合久久| 国产成人久久777777| 99精品国产在热久久无毒不卡| 99久久免费国产精品特黄| 久久久无码精品亚洲日韩软件| 久久精品国产亚洲一区二区| 亚洲国产美女精品久久久久∴| 日韩久久无码免费毛片软件| 久久综合丁香激情久久| 午夜欧美精品久久久久久久| 日日狠狠久久偷偷色综合免费 | 精品国产一区二区三区久久久狼| 久久夜色精品国产亚洲| 久久久久久亚洲精品无码| 91精品国产91久久久久久蜜臀| 久久精品人人槡人妻人人玩AV| 色婷婷综合久久久久中文一区二区| 亚洲日本久久久午夜精品| 九九精品久久久久久噜噜| 久久久久国产一区二区| 亚洲国产成人久久一区WWW| 欧美激情精品久久久久久| 色综合久久中文字幕综合网|