思路：二维前缀和

$n\le 200$，因此可以在$O(n^3)$范围内求解

快速求一个矩形区域内的和：使用二维前缀和预处理

最终计算答案的时候，第一层循环枚举矩形长度$len$，第二，三层循环分别枚举矩形的左上角的端点$(x,y)$

对应右下角的端点则为$(x+len-1,y+len-1)$

具体可以参考代码

时间复杂度

$O(n^3)$

C++

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int n;
char a[N][N];
int s[N][N];
int query(int x1,int y1,int x2,int y2){
    return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + (a[i][j]=='1');
    for(int len=1;len<=n;len++){
        int cnt=0;
        for(int x=1;x<=n-len+1;x++){
            for(int y=1;y<=n-len+1;y++){
                int sum=query(x,y,x+len-1,y+len-1);
                if(sum*2==len*len){
                    cnt++;
                }
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    static final int N = 210;
    static int n;
    static char[][] a = new char[N][N];
    static int[][] s = new int[N][N];

    static int query(int x1, int y1, int x2, int y2) {
        return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            String line = scanner.next();
            for (int j = 1; j <= n; j++) {
                a[i][j] = line.charAt(j - 1);
            }
        }

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                int value = a[i][j] == '1' ? 1 : 0;
                s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + value;
            }

        for (int len = 1; len <= n; len++) {
            int cnt = 0;
            for (int x = 1; x <= n - len + 1; x++) {
                for (int y = 1; y <= n - len + 1; y++) {
                    int sum = query(x, y, x + len - 1, y + len - 1);
                    if (sum * 2 == len * len) {
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        }
    }
}

Python

n = int(input())
a = [input() for _ in range(n)]
s = [[0] * (n + 1) for _ in range(n + 1)]

def query(x1, y1, x2, y2):
    return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + (1 if a[i - 1][j - 1] == '1' else 0)

for length in range(1, n + 1):
    cnt = 0
    for x in range(1, n - length + 2):
        for y in range(1, n - length + 2):
            summation = query(x, y, x + length - 1, y + length - 1)
            if summation * 2 == length ** 2:
                cnt += 1
    print(cnt)

题目描述

小美拿到了一个$n\times m$的矩阵，其中每个元素是0或者1。

小美认为一个矩形区域是完美的，当且仅当该区域内0的数量恰好等于1的数量。现在，小美希望你回答有多少个$i\times i$的完美矩形区域。你需要回答$1\le i\le n$的所有答案

输入描述

第一行输入一个正整数$n$，代表矩阵大小

接下来的$n$行，每行输入一个长度为$n$的01串，用来表示矩阵 $1\le n \le 200$

输出描述

输出$n$行，第$i$行输出$i\times i$的完美矩形区域的数量

样例

输入

4
1010
0101
1100
0011

输出

0
7
0
1