This post is written in Chinese. Please consider using Google Translate

这道题可以动态规划。二维的动态规划。

状态定义：G[i][j]为以(i,j)为左上角顶点的正方形的最大边长。

边界条件：G[i][j]为初始读入的矩阵。

状态转移方程： G[i][j]=min{ G[i+1][j] , G[i][j+1] , G[i+1][j+1] } + 1;

解析： G[i+1][j] , G[i][j+1] , G[i+1][j+1]分别为(i,j)向下、向右、向右下一格的状况。在(n-1,n-1)当且仅当三者都为1的时候，正方形才能扩充。从最右下向上，依次扩充即可。

USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: range LANG: C++

Compiling... Compile: OK

Executing... Test 1: TEST OK [0.000 secs, 3088 KB] Test 2: TEST OK [0.011 secs, 3092 KB] Test 3: TEST OK [0.000 secs, 3092 KB] Test 4: TEST OK [0.000 secs, 3092 KB] Test 5: TEST OK [0.022 secs, 3088 KB] Test 6: TEST OK [0.011 secs, 3092 KB] Test 7: TEST OK [0.022 secs, 3088 KB]

All tests OK.

/*
ID: cmykrgb1
PROG: range
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAXN 251
using namespace std;
ifstream fi("range.in");
ofstream fo("range.out");
int G[MAXN][MAXN],n;
long ans[MAXN];

void init()
{
    long i,j;
    char c;
    fi >> n;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            c=10;
            while (c==10 || c==13) c=fi.get();
            G[i][j]=c-48;
        }
    }
}

long min3(long a,long b,long c)
{
    long k=a;
    if (b<k) k=b;
    if (c<k) k=c;
    return k;
}

void dynamic()
{
    long i,j,k;
    for (i=n-1;i>=1;i--)
    {
        for (j=n-1;j>=1;j--)
        {
            if (G[i][j])
                G[i][j]=min3(G[i+1][j],G[i][j+1],G[i+1][j+1])+1;
            if (G[i][j]>1)
                for (k=2;k<=G[i][j];k++)
                    ans[k]++;
        }
    }
}

void print()
{
    long i,j;
    for (i=2;i<=MAXN;i++)
    {
        if (ans[i])
            fo << i << ' ' << ans[i] << endl;
    }
    fi.close();
    fo.close();
}

int main()
{
    init();
    dynamic();
    print();
    return 0;
}