USACO 2.1 The Carstle

This problem is a typical graph / grid search problem and the solution is also obvious (flood fill is your best friend.). The challenge is to properly transform the problem into right data structure.

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 55;

char dir;
bool visited[maxn][maxn] = {false};
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int N, M, t, row, col, color = 1, rSize = -1, maxSize = -1;

vector<int> roomSize(maxn * maxn, 0);
// last dimension - Index 0/1/2/3 walls 4 color.
int castle[maxn][maxn][5] = {0};

void floodFill(int x, int y) {
visited[x][y] = true;
++roomSize[color];
castle[x][y][4] = color;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (visited[nx][ny] || castle[x][y][i]) continue;

floodFill(nx, ny);
}
}

void merge(int x, int y) {
int sum;
if (x >= 1 && castle[x - 1][y][4] != castle[x][y][4]) {
sum = roomSize[castle[x - 1][y][4]] + roomSize[castle[x][y][4]];
if (sum > maxSize) {
maxSize = sum;
row = x, col = y, dir = 'N';
}
}

if (y < M - 1 && castle[x][y + 1][4] != castle[x][y][4]) {
sum = roomSize[castle[x][y + 1][4]] + roomSize[castle[x][y][4]];
if (sum > maxSize) {
maxSize = sum;
row = x, col = y, dir = 'E';
}
}
}

int main() {
ifstream fin("castle.in");
ofstream fout("castle.out");

fin >> M >> N;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
fin >> t;
for (int k = 3; k >= 0; --k) {
castle[i][j][k] = t%2;
t >>= 1;
}
castle[i][j][4] = 0;
}
}

for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (!visited[i][j]) {
floodFill(i, j);
++color;
}
}
}

rSize = *max_element(roomSize.begin(), roomSize.end());

for (int i = 0; i < M; ++i) {
for (int j = N - 1; j >= 0; --j)
merge(j, i);
}

fout << color - 1 << endl;
fout << rSize << endl;
fout << maxSize << endl;
fout << row + 1 << " " << col + 1 << " " << dir << endl;

return 0;
}