Cod sursă (job #419616)

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

ifstream in("hex.in");
ofstream out("hex.out");

const int dx[8] = {-1, -1, 0, 0, 1, 1};
const int dy[8] = {0, 1, -1, 1, -1, 0};
int n, x[510 * 510], y[510 * 510];
queue <int> q;
char c[510][510];
bool viz[510][510];

int f(int x, int y) {
	return (x - 1) * n + y;
}

pair <int, int> finv(int x) {
	pair <int, int> rs;
	rs.fi = x / n;
	rs.se = x % n;
	if (!rs.se) {
		rs.se = n;
	} else rs.fi++;
	return rs;
}

bool ok(int x, int y, int cod) {
	if (x < 1 || x > n || y < 1 || y > n || viz[x][y] || c[x][y] != cod)
		return 0;
	return 1;
}

bool check(int id) {
	memset(viz, 0, sizeof viz);
	memset(c, 0, sizeof c);
	while (q.size())
		q.pop();
	for (int i = 1; i <= id; i++)
		c[x[i]][y[i]] = (i % 2) + 1;
	for (int i = 1; i <= n; i++)
		if (c[i][1] == 2) {
			q.push(f(i, 1));
			viz[i][1] = 1;
		}
	pair <int, int> p;
	int nod, px, py;
	while (q.size()) {
		nod = q.front();
		q.pop();
		p = finv(nod);
		if (p.se == n) 
			return 1;
		for (int i = 0; i < 8; i++) {
			px = p.fi + dx[i];
			py = p.se + dy[i];
			if (ok(px, py, 2)) {
				q.push(f(px, py));
				viz[px][py] = 1;
			}
		}
	}
	while (q.size())
		q.pop();
	for (int i = 1; i <= n; i++)
		if (c[1][i] == 1) {
			q.push(f(1, i));
			viz[1][i] = 1;
		}
	while (q.size()) {
		nod = q.front();
		q.pop();
		p = finv(nod);
		if (p.fi == n) 
			return 1;
		for (int i = 0; i < 8; i++) {
			px = p.fi + dx[i];
			py = p.se + dy[i];
			if (id == 7) {
			}
			if (ok(px, py, 1)) {
				q.push(f(px, py));
				viz[px][py] = 1;
			}
		}
	}
	return 0;
}

int main() {
	in >> n;
	for (int i = 1; i <= n * n; i++) 
		in >> x[i] >> y[i];
	int st = 1, dr = n * n, mid;
	while (st <= dr) {
		mid = st + dr >> 1;
		if (check(mid))
			dr = mid - 1;
		else st = mid + 1;
	}
	out << st;
	return 0;
}