PROG-1064: Cromatie School

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n,m;
char ar[74][74];
int keep[74][74],color[74][74];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
bool position(int i,int j){
    return i>=1 and j>=1 and i<=n and j<=m;
}
bool found_T(int ui,int i,int uj,int j){
    for(int x=i;x<=ui;x++){
        for(int y=j;y<=uj;y++){
            if(ar[x][y]=='T') return false;
        }
    }
    return true;
}
int f(int ui,int uj){
    int cnt=0,i=ui,j=uj;
    while(found_T(ui,i,uj,j)){
        cnt++;
        i--;
        j--;
        if(!position(i,j)) break;
    }
    return cnt;
}
void dfs(int i,int j,int c){
    if(color[i][j]!=0 or ar[i][j]!='P')
        return ;
    color[i][j]=c;
    for(int d=0;d<4;d++){
        int vi,vj;
        vi=i+dx[d];
        vj=j+dy[d];
        if(position(vi,vj)) dfs(vi,vj,c);
    }
}

int main(){

    scanf("%d%d",&m,&n);
    int mx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf(" %c",&ar[i][j]);
            if(ar[i][j]=='T') continue;
            keep[i][j]=f(i,j);
            mx = max(mx , keep[i][j] );
        }
    }
    printf("%d ",mx*mx);

    int c=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(color[i][j]==0 && ar[i][j]=='P') {
                dfs(i,j,c);
                c++;
            }
        }
    }

    int mn=INF;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(keep[i][j]==mx){
                map <int,int> cnt;
                for(int x=i;x>=i-mx+1;x--){
                    for(int y=j;y>=j-mx+1;y--){
                        if(ar[x][y]=='P') cnt[ color[x][y] ]++;
                    }
                }
                int sz=cnt.size();
                mn=min(mn,sz);
            }
        }
    }

    printf("%d ",mn);
    return 0;
}