TOI14: Space 1

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3;

bool board[N + 10][N + 10];
int row, col;

int main(){

    scanf("%d %d", &col, &row);
    for(int i = 1; i <= row; ++i){
        for(int j = 1; j <= col; ++j){
            char tmpChar;
            scanf(" %c", &tmpChar);
            if(tmpChar == '1'){
                board[i][j] = true;
            }
        }
    }

    int square, triangle, diamond;
    square = triangle = diamond = 0;

    for(int i = 1; i <= row; ++i){
        for(int j = 1; j <= col; ++j){
            if(!board[i][j]){
                continue;
            }
            if(board[i][j + 1] && board[i + 1][j]){ // Square
                ++square;
                int sz = 0;
                int ti = i;
                while(board[ti][j]){
                    ++sz;
                    ++ti;
                }
                for(int ti = i; ti <= i + sz - 1; ++ti){
                    for(int tj = j; tj <= j + sz - 1; ++tj){
                        board[ti][tj] = false;
                    }
                }
            } else if(board[i + 1][j - 1] && board[i + 1][j] && !board[i + 1][j + 1]){ // Triangle Left
                ++triangle;
                int sz = 0;
                int ti = i;
                int tj = j;
                while(board[ti][tj]){
                    ++sz;
                    ++ti;
                    --tj;
                }
                for(int ti = i; ti <= i + sz + sz - 2; ++ti){
                    if(ti - i <= sz - 1){
                        for(int tj = j - (ti - i); tj <= j; ++tj){
                            board[ti][tj] = false;
                        }
                    } else {
                        for(int tj = j - (i + sz + sz - 2 - ti); tj <= j; ++tj){
                            board[ti][tj] = false;
                        }
                    }
                }
            } else if(board[i + 1][j] && board[i + 1][j + 1] && !board[i + 1][j - 1]){ // Triangle Right
                ++triangle;
                int sz = 0;
                int ti = i;
                int tj = j;
                while(board[ti][tj]){
                    ++sz;
                    ++ti;
                    ++tj;
                }
                for(int ti = i; ti <= i + sz + sz - 2; ++ti){
                    if(ti - i <= sz - 1){
                        for(int tj = j; tj <= j + (ti - i); ++tj){
                            board[ti][tj] = false;
                        }
                    } else {
                        for(int tj = j; tj <= j + (i + sz + sz - 2 - ti); ++tj){
                            board[ti][tj] = false;
                        }
                    }
                }
            } else if(board[i][j + 1] && board[i + 1][j + 1]){ // Triangle Down
                ++triangle;
                int sz = 0;
                int ti = i;
                int tj = j;
                while(board[ti][tj]){
                    ++sz;
                    ++ti;
                    ++tj;
                }
                for(int ti = i; ti <= i + sz - 1; ++ti){
                    for(int tj = j - (i - ti); tj <= (j + sz - 1) + (i + sz - 1 - ti); ++tj){
                        board[ti][tj] = false;
                    }
                }
            } else if(board[i + 1][j - 1] && board[i + 1][j + 1]){ // Triangle Up / Diamond
                int sz = 0;
                int ti = i;
                int tj = j;
                while(board[ti][tj]){
                    ++sz;
                    ++ti;
                    ++tj;
                }
                if(board[ti][tj - 2]){ // Diamond
                    ++diamond;
                    for(int ti = i; ti <= i + sz + sz - 2; ++ti){
                        if(ti - i <= sz - 1){
                            for(int tj = j - (ti - i); tj <= j + (ti - i); ++tj){
                                board[ti][tj] = false;
                            }
                        } else {
                            for(int tj = j - (i + sz + sz - 2 - ti); tj <= j + (i + sz + sz - 2 - ti); ++tj){
                                board[ti][tj] = false;
                            }
                        }
                    }
                } else { // Triangle Up
                    ++triangle;
                    for(int ti = i; ti <= i + sz - 1; ++ti){
                        for(int tj = j - (ti - i); tj <= j + (ti - i); ++tj){
                            board[ti][tj] = false;
                        }
                    }
                }
            }
        }
    }

    cout << square << " " << diamond << " " << triangle;

    return 0;
}