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 幻浪天空领主 阅读(240) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年6月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

常用链接

留言簿(1)

随笔档案(2)

文章分类(23)

文章档案(22)

搜索

最新评论

阅读排行榜

评论排行榜