USACO : The Castle

/*
ID: tausiq11
PROG: castle
LANG: C++
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 50
#define LL long long

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Pr(x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++) cout << *it << " "; cout << endl;
#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

using namespace std;

enum direction { West = 1, North = 2, East = 4, South = 8 };

int width, height;

int maze [N + 2] [N + 2];
vector <int> matrix [N * N + 5];
bool vis [N * N + 5];
int numberOfComponent;
int component [N * N + 5];
int componentFrequency [N * N + 5];
int dr [] = {-1, 0, 1, 0};
int dc [] = {0, 1, 0, -1};
int maxSizedRoom;
int resW, resH;
char resDir;

void reset ()
{
	int cnt = 1;

	for ( int i = 0; i < height; i++ ) {
		for ( int j = 0; j < width; j++ ) maze [i] [j] = cnt++;
	}

	Set (vis, false);
	numberOfComponent = 0;
	Set (componentFrequency, 0);
	maxSizedRoom = -1;
}

void checkByRemove (int p, int q)
{
	int freq = -1;

	// printf ("%d\n", maze [p] [q]);

	if ( p != 0 && component [maze [p] [q]] != component [maze [p - 1] [q]] ) {
		freq = componentFrequency [component [maze [p] [q]]] + componentFrequency [component [maze [p - 1] [q]]];
		if ( freq > maxSizedRoom ) {
			maxSizedRoom = freq;
			resW = q; resH = p; resDir = 'N';
		}
	}
	if ( q != width - 1 && component [maze [p] [q]] != component [maze [p] [q + 1]] ) {
		freq = componentFrequency [component [maze [p] [q]]] + componentFrequency [component [maze [p] [q + 1]]];
		if ( freq > maxSizedRoom ) {
			maxSizedRoom = freq;
			resW = q; resH = p; resDir = 'E';
		}
	}
}

void dfs (int node, int c)
{
	if ( vis [node] ) return;
	vis [node] = true;
	component [node] = c;

	for ( size_t i = 0; i < matrix [node].size (); i++ ) {
		dfs (matrix [node] [i], c);
	}
}

void print ()
{
	for ( int i = 1; i <= 28; i++ ) {
		printf ("%d -> ", i);
		for ( size_t j = 0; j < matrix [i].size(); j++ ) {
			printf ("%d ", matrix [i] [j]);
		}
		printf ("\n");
	}
}

void print2 ()
{
	for ( int i = 1; i <= 28; i++ ) {
		printf ("%d -> %d\n", i, component [i]);
	}
}

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

	scanf ("%d %d", &width, &height);
	int inp;

	reset ();

	bool dir [4];

	for ( int i = 0; i < height; i++ ) {
		for ( int j = 0; j < width; j++ ) {
			scanf ("%d", &inp);
			dir [0] = dir [1] = dir [2] = dir [3] = true;
			for ( int k = 8; k >= 1; k /= 2 ) {
				if ( inp >= k ) {
					switch (k) {
					case 8: dir [0] = false; break;
					case 4: dir [1] = false; break;
					case 2: dir [2] = false; break;
					case 1: dir [3] = false; break;
					}
					inp -= k;
				}
			}

			if ( dir [0] ) matrix [maze [i] [j]].push_back(maze [i + 1] [j]);
			if ( dir [1] ) matrix [maze [i] [j]].push_back(maze [i] [j + 1]);
			if ( dir [2] ) matrix [maze [i] [j]].push_back(maze [i - 1] [j]);
			if ( dir [3] ) matrix [maze [i] [j]].push_back(maze [i] [j - 1]);
		}
	}

	// print ();

	for ( int i = 0; i < height; i++ ) {
		for ( int j = 0; j < width; j++ ) {
			if ( !vis [maze [i] [j]] ) {
				dfs (maze [i] [j], ++numberOfComponent);
			}
		}
	}

	// print2 ();


	printf ("%d\n", numberOfComponent); // number of room

	for ( int i = 0; i < N * N + 2; i++ ) {
		componentFrequency [component [i]]++;
	}

	int largestComponent = -1;

	for ( int i = 1; i <= numberOfComponent; i++ ) {
		largestComponent = max (largestComponent, componentFrequency [i]);
	}

	printf ("%d\n", largestComponent);	// largest room

	for ( int j = 0; j < width; j++ ) {
		for ( int i = height - 1; i >= 0; i-- ) {
			checkByRemove (i, j);
		}
	}

	printf ("%d\n%d %d %c\n", maxSizedRoom, resH + 1, resW + 1, resDir);

	return 0;
}

// @END_OF_SOURCE_CODE