IOI '94 P2 - The Castle

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> g, component;
vector<int> cSize;
pair<int, int> direction[4] {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

int dfs(int i, int j, int c) {
    component[i][j] = c;
    int cnt = 1;
    for (int dir = 0; dir < 4; ++dir) {
        int ii = i+direction[dir].first, jj = j+direction[dir].second;
        if (!(g[i][j] & (1 << dir)) && component[ii][jj] == -1) { // no wall in this direction
            cnt += dfs(ii, jj, c);
        }
    }
    return cnt;
}

int main() {
    int m, n;
    cin >> m >> n;
    g.resize(n), component.resize(n);
    for (int i = 0; i < n; ++i) {
        g[i].resize(m);
        component[i] = vector<int>(m, -1);
        for (int j = 0; j < m; ++j) cin >> g[i][j];
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (component[i][j] == -1) cSize.push_back(dfs(i, j, cSize.size()));
        }
    }
    cout << cSize.size() << endl << *max_element(cSize.begin(), cSize.end()) << endl;

    int maxSize = 0; string maxWall = "";
    for (int j = 0; j < m; ++j) {
        for (int i = n-1; i >= 0; --i) {
            for (int dir = 1; dir <= 2; ++dir) {
                int ii = i + direction[dir].first, jj = j + direction[dir].second;
                if (ii < 0 || jj >= m) continue;
                if (component[i][j] == component[ii][jj]) continue;
                int curSize = cSize[component[i][j]] + cSize[component[ii][jj]];
                if (curSize > maxSize) {
                    maxSize = curSize;
                    maxWall = to_string(i+1) + " " + to_string(j+1) + " " + string(1, 'N' + (dir-1)*('E'-'N'));
                }
            }
        }
    }
    cout << maxSize << endl << maxWall << endl;
    return 0;
}