Cod sursă (job #574557)

#include <fstream>
#include <string.h>
#include <climits>

#define NMAX 501

using namespace std;

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

int n;
short x, y;
short viz[NMAX][NMAX];
short mini[NMAX * NMAX], maxi[NMAX * NMAX];
int tata[NMAX * NMAX];

int dx[] = {-1, -1, 0, 1, 1, 0};
int dy[] = {0, 1, 1, 0, -1, -1};

int getRoot(int x, int y)
{
    int val = (x - 1) * n + y;
    int found = 0;

    while(tata[val] > 0)
    {
        val = tata[val];
    }

    found = val;
    val = (x - 1) * n + y;

    while(tata[val] > 0)
    {
        int aux = tata[val];
        tata[val] = found;
        val = aux;
    }

    return found;
}

void joinRoots(int root_1, int root_2)
{
    tata[root_1] = root_2;
    mini[root_2] = min(mini[root_2], mini[root_1]);
    maxi[root_2] = max(maxi[root_2], maxi[root_1]);
}

int main()
{
    f >> n;

    for(int i = 1; i <= n * n; i++)
        mini[i] = 501;
    for(int i = 1; i <= n * n; i++)
    {
        f >> x >> y;

        viz[x][y] = i % 2 + 1;
        for(int j = 0; j < 6; j++)
        {
            int new_x = x + dx[j];
            int new_y = y + dy[j];

            if(new_x >= 1 && new_x <= n && new_y >= 1 && new_y <= n && viz[new_x][new_y] == i % 2 + 1)
            {
                int root_1 = getRoot(x, y);
                int root_2 = getRoot(new_x, new_y);

                if(root_1 != root_2)
                {
                    joinRoots(root_1, root_2);
                }
            }
        }

        int new_root = getRoot(x, y);

        if(i % 2 == 1)
        {
            mini[new_root] = min(mini[new_root], y);
            maxi[new_root] = max(maxi[new_root], y);
        }
        else
        {
            mini[new_root] = min(mini[new_root], x);
            maxi[new_root] = max(maxi[new_root], x);
        }

        if(mini[new_root] == 1 && maxi[new_root] == n)
        {
            g << i << "\n";
            return 0;
        }
    }

    return 0;
}