USACO 2.1.1 – The Castle

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int graph[54][54], color[54][54], size[54 * 54], M, N, best = 0, best_merged = 0;
int di[4][2] = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } }, i_m, j_m, d_m, comp=0;
char dir[5] = "WNES";

int main() {
	freopen("castle.in", "r", stdin), freopen("castle.out", "w", stdout);
	memset(graph, 0, sizeof graph), memset(color, 0, sizeof color), memset(size, 0, sizeof size);
	scanf("%d %d", &M, &N);
	for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) scanf("%d", graph[i] + j);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			if (color[i][j])
				continue;
			color[i][j] = ++comp, size[comp] = 1, best = max(best, size[comp]);
			queue<pair<int, int> > q; q.push(make_pair(i, j));
			while (q.size()) {
				pair<int, int> p = q.front();
				q.pop();
				for (int d = 0; d < 4; d++)
					if (!(graph[p.first][p.second] & (1 << d))) {
						int i_ = p.first + di[d][0], j_ = p.second + di[d][1];
						if (i_ >= 0 && i_ < N && j_ >= 0 && j_ < M && !color[i_][j_]) {
							color[i_][j_] = comp, best = max(best, ++size[comp]);
							q.push(make_pair(i_, j_));
						}
					}
			}
		}

	for (int j = 0; j < M; j++)
		for (int i = N-1; i >=0; i--)
			for (int d = 1; d < 3; d++)
				if ((graph[i][j] & (1 << d))) {
					int i_ = i + di[d][0], j_ = j + di[d][1];
					if (i_ >= 0 && i_ < N && j_ >= 0 && j_ < M)
						if (color[i][j] != color[i_][j_] && size[color[i][j]] + size[color[i_][j_]] > best_merged)
							best_merged = size[color[i][j]] + size[color[i_][j_]], i_m = i, j_m = j, d_m = d;
				}

	printf("%d\n%d\n%d\n", comp, best, best_merged);
	printf("%d %d %c\n", i_m+1, j_m+1, dir[d_m]);

	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: