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

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邊形個數，（每個單位正方形可以被重復利用）。

代碼：