AcWing1387 家的范围

通过反证法可得,当f[i][j] == 1时，f[i][j] = min(f[i - 1][j], f[i - 1][j - 1], f[i][j - 1]) + 1
时间复杂度:O($n^3$)，通过前缀和可优化成O($n^2$)

#include<iostream>
using namespace std;

const int N = 255;
char g[N][N];
int f[N][N], n, res[N];

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++ )cin >> g[i] + 1;
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= n ; j ++ )
            if(g[i][j] == '1')
                f[i][j] = min(f[i - 1][j], min(f[i - 1][j - 1], f[i][j - 1])) + 1;

    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= n ; j ++ )
            for(int k = 2 ; k <= f[i][j] ; k ++ )
                res[k] ++;

    for(int i = 2 ; res[i] ; i ++ )cout << i << ' ' << res[i] << endl;
    return 0;
}