算法一:

时间复杂度: $O(n^3)$

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int N=300;

int n;
char g[N][N];
bool dp[N][N][N];

int cnt[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){
            dp[1][i][j]=g[i][j]-'0';
        }
    }

    for(int k=2;k<=n;++k){
        for(int i=k;i<=n;++i){
            for(int j=k;j<=n;++j){
                if(dp[k-1][i-1][j]&&dp[k-1][i-1][j-1]&&dp[k-1][i][j-1]&&g[i][j]=='1'){
                    dp[k][i][j]=1;
                    cnt[k]++;
                }
            }
        }
    }

    for(int i=2;i<=n;++i){
        if(cnt[i]) cout<<i<<" "<<cnt[i]<<"\n";
    }

    return 0;
}

算法二:

时间复杂度: $O(n^2)$

$f(i,j)$ 表示右下角坐标为 $(i,j)$ 的点能够形成的最大矩形

$f(i,j)=min(f(i,j-1),f(i-1,j),f(i-1,j-1))+1$

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int N=300;

int n;
char g[N][N];
int f[N][N];

int cnt[N];
int ans[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){
            cnt[f[i][j]]++;
        }
    }

    //前缀和优化
    for(int i=n;i>1;--i) ans[i]=cnt[i]+ans[i+1];

    for(int i=2;i<=n;++i){
        if(ans[i]) cout<<i<<" "<<ans[i]<<"\n";
    }

    return 0;
}