PROG-1074: Mravojed

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
int n,m;
char ar[102][102];
int color[102][102];
int line[102],col[102];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int position(int i,int j){
    return i>=1 and i<=n and j>=1 and j<=m;
}
bool all(int ui,int i,int uj,int j){
    for(int k=uj;k<=j;k++) {
        if(ar[i][k]!='x')
            return false;
    }
    for(int k=ui;k<=i;k++){
        if(ar[k][j]!='x')
            return false;
    }
    return true;
}
int first_square(int ui,int uj){
    int i=ui,j=uj,cnt=0;
    while(ar[ui][j]=='x' and ar[i][uj]=='x' and all(ui,i,uj,j)){
        i++;
        j++;
        cnt++;
        if(!position(i,j) ) break;
    }
    return cnt;
}
pii second_square(int ui,int uj){
    queue <pair<int,int>> q;
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;j--){
            if(ar[i][j]=='x'){
                q.push({i,j});
                break;
            }
        }
    }
    int ui2,uj2;
    ui2=0;
    uj2=0;
    vector < vector<bool> > visited(n+1,vector<bool> (m+1,false));
    while(q.size()>0){
        int ui,uj;
        ui=q.front().first;
        uj=q.front().second;
        q.pop();
        if(visited[ui][uj])
            continue;
        ui2=max(ui2,ui);
        uj2=max(uj2,uj);
        visited[ui][uj]=true;
        for(int i=0;i<4;i++){
            int vi,vj;
            vi=ui+dx[i];
            vj=uj+dy[i];
            if(position(vi,vj) and !visited[vi][vj] and ar[vi][vj]=='x'){
                q.push({vi,vj});
            }
        }
    }
    return {ui2,uj2};
}
int sz(int ui,int uj){
    int cnt=0;
    /*while(line[ui]>0||col[uj]>0){
        cnt=max(cnt,line[ui]);
        cnt=max(cnt,col[uj]);
        ui++;
        uj++;
        if(!position(ui,uj)) break;
    }*/
    while(line[ui]>0){
        cnt=max(cnt,line[ui]);
        ui++;
        if(ui>n) break;
    }
    while(col[uj]>0){
        cnt=max(cnt,col[uj]);
        uj++;
        if(uj>m) break;
    }
    return cnt;
}
int main(){

    scanf("%d%d",&n,&m);
    int ui1=0,uj1=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf(" %c",&ar[i][j]);
            if(ar[i][j]=='x' and ui1==0 and uj1==0){
                ui1=i;
                uj1=j;
            }
            if(ar[i][j]=='x'){
                line[i]++;
                col[j]++;
            }
        }
    }

    int square1=first_square(ui1,uj1);
    printf("%d %d %d\n",ui1,uj1,square1);

    for(int i=ui1;i<=ui1+square1-1;i++){
        for(int j=uj1;j<=uj1+square1-1;j++){
            ar[i][j]='.';
            line[i]--;
            col[j]--;
        }
    }

    int ui2,uj2,square2;
    pii uij=second_square(0,0);
    ui2=uij.first;
    uj2=uij.second;
    square2=sz(ui2,uj2);
    if(square2==0) printf("%d %d %d",ui1,uj1,square1);
    else {
        if(uj2==1) printf("%d %d %d",ui2-square2+1,uj2,square2);
        else printf("%d %d %d",ui2-square2+1,uj2-square2+1,square2);
    }


    return 0;
}
/*
----------

case :  PPPPPPPP-P
5 5
.xxxx
xxxxx
xxxxx
xxxxx
.....

----------

3 5
xxxxx
xxxxx
xxxxx

----------

5 4
xxxx
xxxx
xxxx
xxxx
xxx.
correct

5 5
.....
xxx..
xxxx.
xxxx.
.xxx.
correct

----------

3 3
xxx
xxx
xx.

5 5
.....
.xxx.
.xxx.
.xxx.
.x...

3 3
.xx
xxx
xx.

3 3
xx.
xx.
x..

3 3
xx.
xxx
...

3 3
..x
.xx
.xx
*/