Cod sursă (job #310659)

#include <cstdio>

#define MAX_N 500
#define NEAR 6
#define DIR 4

using namespace std;

FILE *f, *g;

int n;

char a[MAX_N + 1][MAX_N + 1];

int stk[MAX_N * MAX_N + 1];

int tata[MAX_N * MAX_N + 1];

bool poz[MAX_N * MAX_N + 1][DIR + 1];

const int dl[] = {0, -1, -1, 0, 1, 1, 0};
const int dc[] = {0, 0, 1, 1, 0, -1, -1};

///s-ar putea sa crape stiva recursiva
int getRoot(int cod)
{
    int stkLen = 0;

    int cr = cod;
    while(cr != 0)
    {
        stk[++ stkLen] = cr;

        cr = tata[cr];
    }

    int root = stk[stkLen];

   // printf("AVEM ROOT %d\n", root);

    stkLen --;
    while(stkLen > 0)
    {
       // printf("NIME\n");

        tata[stk[stkLen]] = root;

        stkLen --;
    }

    return root;
}

void corner(int l, int c, int root)
{
    poz[root][1] |= (l == 1);
    poz[root][2] |= (c == n);
    poz[root][3] |= (l == n);
    poz[root][4] |= (c == 1);
}

bool win(int i, int root)
{
   // printf("VERIFICIAM %d, %d  %d %d\n", root, i, poz[root][i + 1], poz[root][i + 3]);

    return (poz[root][i + 1] == 1 && poz[root][i + 3] == 1);
}

int cod(int l, int c)
{
    return ((l - 1) * n + c);
}

void uneste(int a, int b)
{
    if(a != b)
    {
        tata[b] = a;

       // printf("UNIM ROROOROROROROROORORORO %d %d\n", a, b);

        int dir;
        for(dir = 1; dir <= DIR; dir ++)
        {
            poz[a][dir] = poz[b][dir] = (poz[a][dir] | poz[b][dir]);
        }
    }
}

bool inMat(int l, int c)
{
    return (l >= 1 && l <= n && c >= 1 && c <= n);
}

int rez;

void readFile()
{
    f = fopen("hex.in", "r");

    fscanf(f, "%d", &n);

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
            a[i][j] = -1;
    }

    int nn = n * n;

    int i = 1;
    int l, c;
    int root;
    int newLine, newCol;
    int dir;
    while(i <= nn && rez == 0)
    {
        //printf("%d\n", i);

        fscanf(f, "%d%d", &l, &c);

        root = getRoot(cod(l, c));

        corner(l, c, root);

        a[l][c] = i & 1;

        for(dir = 1; dir <= NEAR; dir ++)
        {
            newLine = l + dl[dir];
            newCol = c + dc[dir];

            if(inMat(newLine, newCol))
            {
                if(a[newLine][newCol] == a[l][c])
                {
                   // printf("+++++++UNIM %d %d  %d %d\n", l, c, newLine, newCol);

                    uneste(root, getRoot(cod(newLine, newCol)));
                }
            }
        }

        if(win(i & 1, root))
        {
            rez = i;
        }

        i ++;
    }

    fclose(f);
}

void printFile()
{
    g = fopen("hex.out", "w");

    fprintf(g, "%d\n", rez);

    fclose(g);
}

int main()
{
    readFile();

    printFile();

    return 0;
}