USACO-T021: The Castle

/*
ID: mickyta1
TASK: castle
LANG: C++
*/

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

#define r first
#define c second
typedef pair<int, int> pii;
typedef tuple<pii, pii, char> tppc;

const int N = 50 + 5;
const int NN = 2500 + 5;
const pii dir[4] = {pii(0, -1), pii(-1, 0), pii(0, 1), pii(1, 0)}; // W N E S

vector<tppc> walls;
int board[N][N], cVertex[N][N], dens[NN], row, col;
bool visited[N][N];

bool isInBoard(int r, int c){
    return r >= 1 && r <= row && c >= 1 && c <= col;
}

void BFS(pii st, int i){
    queue<pii> que;
    visited[st.r][st.c] = true;
    cVertex[st.r][st.c] = i;
    que.push(st);
    while(!que.empty()){
        int ur = que.front().r;
        int uc = que.front().c;
        que.pop();
        ++dens[i];
        for(int d = 0; d < 4; ++d){
            int vr = ur + dir[d].r;
            int vc = uc + dir[d].c;
            if((board[ur][uc] & (1 << d)) == 0 && !visited[vr][vc]){
                visited[vr][vc] = true;
                cVertex[vr][vc] = i;
                que.emplace(vr, vc);
            }
        }
    }
}

int main(){
    freopen("castle.in", "r", stdin);
    freopen("castle.out", "w", stdout);

    scanf("%d%d", &col, &row);
    for(int i = 1; i <= row; ++i){
        for(int j = 1; j <= col; ++j){
            scanf("%d", &board[i][j]);
            if((board[i][j] & (1 << 1)) != 0 && isInBoard(i - 1, j)){ // N
                walls.emplace_back(pii(i, j), pii(i - 1, j), 'N');
            }
            if((board[i][j] & (1 << 2)) != 0 && isInBoard(i, j + 1)){ // E
                walls.emplace_back(pii(i, j), pii(i, j + 1), 'E');
            }
        }
    }
    int roomCnt = 0;
    int mxDens = 0;
    for(int i = 1; i <= row; ++i){
        for(int j = 1; j <= col; ++j){
            if(!visited[i][j]){
                BFS(pii(i, j), ++roomCnt);
                mxDens = max(mxDens, dens[roomCnt]);
            }
        }
    }
    cout << roomCnt << '\n' << mxDens << '\n';
    int mx = 0;
    pii ans;
    char di;
    for(tppc e : walls){
        pii u = get<0>(e);
        pii v = get<1>(e);
        char d = get<2>(e);
        if(cVertex[u.r][u.c] == cVertex[v.r][v.c]){
            continue;
        }
        int sz = dens[cVertex[u.r][u.c]] + dens[cVertex[v.r][v.c]];
        if(sz > mx){
            mx = sz;
            ans = u;
            di = d;
        } else if(sz == mx){
            if(u.c < ans.c){
                ans = u;
                di = d;
            } else if(u.c == ans.c){
                if(u.r > ans.r){
                    ans = u;
                    di = d;
                } else if(u.r == ans.r){
                    if(d == 'N' && di == 'E'){
                        di = d;
                    }
                }
            }
        }
    }
    cout << mx << '\n' << ans.r << ' ' << ans.c << ' ' << di << '\n';

    fclose(stdin);
    fclose(stdout);
    return 0;
}