code/MeiTuan1/question2.cpp

// #include <iostream>  
// #include <string>  
// using namespace std;  
// int main() {  
//     string s;  
//     getline(cin, s);  
//     for (size_t i = 0; i < s.length() - 1; ++i) {  
//         if (s[i] == 'm' || s[i] == 'M') {  
//             if (s[i + 1] == 't' || s[i + 1] == 'T') {  
//                 s.replace(i, 2, "$$");  
//                 i++;  
//             }  
//         }  
//     }  
//     cout << s << endl;  
//     return 0;  
// }

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000;
int n;
char str[N][N];
int m[N][N], s[N][N];

int ans[N];

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

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> str[i];
    //数据存储
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (str[i][j] == '1') {
                m[i + 1][j + 1] = 1;
            } else {
                m[i + 1][j + 1] = 0;
            }
        }
    }
    // 计算前缀和
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j  ++) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + m[i][j];
        }
    }
    for (int i = 0; i < n; i ++) { 
        for (int j = 0; j < n; j ++) {
            for (int k = 0; k < n; k ++) {
                if(i + k >= n || j + k >= n) {
                    break;
                }
                int sub = GetPreSub(i, j, i + k, j + k);
                if (sub * 2 == (k + 1) * (k + 1)) {
                    ans[k] ++;
                }
            }
        }
    }
    for (int i = 0; i < n; i ++) cout << ans[i] << endl;
    return 0;
}