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
题意：
给出一个正方形牧场，0表示没草皮，1表示有草皮。
/*
LANG: C
TASK: range
*/
#include<stdio.h>
#define maxn 251
int map[maxn][maxn];
int ans[maxn], n;
int min(int a, int b, int c)
{
int d = a < b ? a : b;
return d < c ? d : c;
}
void dp()
{
int i, j, k;
for (i = n - 1; i >= 1; i--)
{
for (j = n - 1; j >= 1; j--)
{
//表示以map[i][j]为左上角的正map[i][j]边形
if (map[i][j])//当下面和右边以及右下边都是1是，正边形边长加1
{
map[i][j] = min(map[i+1][j+1], map[i+1][j], map[i][j+1]) + 1;
}
if (map[i][j] > 1)//对于边数> 2的，累加正变形个数,增加正边形的个数等于map[i][j]边形对角线上的单位正边形个数
{
for (k = 2; k <= map[i][j]; k++)
{
ans[k]++;
}
}
}
}
}
int main()
{
freopen("range.in", "r", stdin), freopen("range.out", "w", stdout);
int i, j;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
scanf("%1d", &map[i][j]);
}
}
dp();
for (i = 2; i <= maxn; i++)
{
if (ans[i])
{
printf("%d %d\n", i, ans[i]);
}
}
fclose(stdin), fclose(stdout);
return 0;
}
求有草皮的正2……n边形个数，（每个单位正方形可以被重复利用）。
代码：