Cod sursă (job #80753)

#include <stdio.h>
#define N_MAX 500

class cell { // Fara aceasta clasa, codul ar fi aratat infiorator
	public:
		short l, c;
		
		cell() // Default constructor
		{
			l = c = 0;
		}
		cell(short _l, short _c) // Foarte util petru introducerea valorilor particulare
		{
			l = _l;
			c = _c;
		}

		bool operator != (cell _cell) // mai bine folosim operator overloading decat sa uratim if-urile
		{
			return l != _cell.l || c != _cell.c;
		}
		bool operator == (cell _cell)
		{
			return l == _cell.l && c == _cell.c;
		}
};

unsigned char type[N_MAX + 2][N_MAX + 2]; // Santinela borduri
cell up[N_MAX + 2][N_MAX + 2]; // Mairicea de Parinti

// Desi functiile nu prea au ce cauta intr-un limbaj obiectual, aici fac codul mai citibil
cell getroot(cell x) // Aflare radacina + compresia caii
{
	cell root;
	for (root = x; up[root.l][root.c] != root; root = up[root.l][root.c]); // Ajungem pana la sef (nu e chiar etic, dar e mai scurt codul)
	
	// Compresia caii
	cell y;
	while (up[x.l][x.c] != x) {
		y = up[x.l][x.c];
		up[x.l][x.c] = root;
		x = y;
	}
	return root;
}

void unify(cell x, cell y)
{
	cell rx = getroot(x), ry = getroot(y);
	up[rx.l][rx.c] = ry;
}

bool query(cell x, cell y)
{
	return getroot(x) == getroot(y);
}

int main()
{
	FILE *fin, *fout;
	fin = fopen("hex.in", "r");
	fout = fopen("hex.out", "w");

	// Citire
	int N;
	fscanf(fin, "%d", &N);

	// Initializare tabla (union-find)
	int i, j;
	for (i = 0; i <= N + 1; i++) {
		for (j = 0; j <= N + 1; j++) {
			up[i][j] = cell(i, j);
			type[i][j] = 13; // Important e sa fie diferit de 0 si 1 (rosu si albastru)
		}
	}
	for (i = 1; i <= N; i++) {
		type[0][i] = type[N + 1][i] = 1; // Sus si jos e albastru
		type[i][0] = type[i][N + 1] = 0; // Stanga si dreapta rosu
		unify(cell(0, i), cell(0, 1));
		unify(cell(N + 1, i), cell(N + 1, 1));
		unify(cell(i, 0), cell(1, 0));
		unify(cell(i, N + 1), cell(1, N + 1));
	}

	int N2 = N * N;
	i = 0;
	while (i < N2 && !(query(cell(0, 1), cell(N + 1, 1)) || query(cell(1, 0), cell(N + 1, 1)))) {
		short lin, col;
		fscanf(fin, "%hd%hd", &lin, &col);
		type[lin][col] = i % 2; // Rosu/Albastru
		if (type[lin - 1][col] == type[lin][col]) { // Trebuie sa fie de acelasi tip ca sa le putem uni
			unify(cell(lin - 1, col), cell(lin, col));
		}
		if (type[lin - 1][col + 1] == type[lin][col]) {
			unify(cell(lin - 1, col + 1), cell(lin, col));
		}
		if (type[lin + 1][col] == type[lin][col]) {
			unify(cell(lin + 1, col), cell(lin, col));
		}
		if (type[lin + 1][col - 1] == type[lin][col]) {
			unify(cell(lin + 1, col - 1), cell(lin, col));
		}
		if (type[lin][col - 1] == type[lin][col]) {
			unify(cell(lin, col - 1), cell(lin, col));
		}
		if (type[lin][col + 1] == type[lin][col]) {
			unify(cell(lin, col + 1), cell(lin, col));
		}
		i++;
	}
	fprintf(fout, "%d\n", i);

	fclose(fin);
	fclose(fout);
	return 0;
}