TOI14: space_1

#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9;
using pii = pair <int, int>;
bool ar[1001][1001];
int n, m;

int Height(int I, int J){
    int cnt = 0;
    for(int i=I;i<=n;i++){
        if(!ar[i][J]) return cnt;
        cnt ++;
    }
    return cnt;
}

int Length(int I, int J){
    int cnt = 0;
    for(int j=J;j<=m;j++){
        if(!ar[I][j]) return cnt;
        cnt ++;
    }
    return cnt;
}

void Square(int I, int J, int H, int L){
    for(int i = I; i <= I+H-1; i++){
        for(int j = J;j <= J+L-1; j++){
            ar[i][j] = false;
        }
    }
}

bool pst(int ui, int uj){
    return ui >= 1 and ui <= n and uj >= 1 and uj <= m;
}

bool Diamond(int I, int J, int H, int L){
    queue <pii> q;
    q.push({I, J});

    vector <int> mn(n+10, INF), mx(n+10, -INF);
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    while(q.size() > 0){
        int ui, uj;
        ui = q.front().first;
        uj = q.front().second;
        q.pop();
        if(!ar[ui][uj])
            continue;
        ar[ui][uj] = false;
        mn[ui] = min(mn[ui], uj);
        mx[ui] = max(mx[ui], uj);
        for(int d = 0; d < 4; d++){
            int vi, vj;
            vi = ui + dx[d];
            vj = uj + dy[d];
            if(pst(vi, vj) and ar[vi][vj]) {
                q.push({vi, vj});
            }
        }
    }

    int idx = 1, cnt = 0, x = I + H/ 2 - 1;
    for(int i = I; i <= I+H-1; i++){
        if(mn[i] == INF or mn[i] == -INF) return false;
        if(mx[i] - mn[i] != cnt) return false;
        idx ++;
        if(i <= x) cnt += 2;
        else cnt -= 2;
    }
    return true;
}

void filled(int I, int J){
    queue <pii> q;
    q.push({I, J});

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    while(q.size() > 0){
        int ui, uj;
        ui = q.front().first;
        uj = q.front().second;
        q.pop();
        if(!ar[ui][uj])
            continue;
        ar[ui][uj] = false;
        for(int d = 0; d < 4; d++){
            int vi, vj;
            vi = ui + dx[d];
            vj = uj + dy[d];
            if(pst(vi, vj) and ar[vi][vj]) {
                q.push({vi, vj});
            }
        }
    }
}

void prt(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ar[i][j]) printf("1");
            else printf("0");
        }
        printf("\n");
    }
    cout << endl;
}

int main(){

    scanf("%d%d", &m, &n);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char x;
            scanf(" %c", &x);
            if(x == '1') ar[i][j] = true;
        }
    }

    int sq = 0, dm = 0, tri = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!ar[i][j]) continue;
            int H, L;
            H = Height(i, j);
            L = Length(i, j);
            if(H == L) {
                Square(i, j, H, L);
                sq ++;
            }
            else if((H > 2 or L > 2) and Diamond(i, j, H, L)) {
                dm ++;
            }
            else {
                filled(i, j);
                tri ++;
            }
        }
    }

    printf("%d %d %d\n", sq, dm, tri);

    return 0;
}