Cod sursă (job #293922)

#include <stdio.h>

#define Smerenie 255025
#define Nadejde 505
#define MAX_DIR 6
#define MAX_COORD 4

#define NORTH 0
#define SOUTH 1
#define EAST 2
#define WEST 3
#define INDEX(U, V) ((U) * (N + 1) + (V))

/**  Algoritm problema "Hex", autor Catalin Francu:
 *  Cand se face o mutare (u, v), vezi ce hexagoane de pe margine se ating.
 *  Apoi, treci prin vecini si te conectezi cu toti cei care s-au conectat cu vecinii tai.
 *  La fiecare pas verificam daca nordul si sudul sau estul si vestul sunt conectati.
 *  Multumim Doamne!
 **/

int N, ss;
int boss[Smerenie];              /// boss[i] este seful codului "i".
int stack[Smerenie];             /// stiva union-find.
char round[2] = {'A', 'R'};      /// retine cui ii este randul.
char board[Nadejde][Nadejde];    /// board retine mutarile.
char touch[MAX_COORD][Smerenie]; /// touch[i][j] este 1 doar daca codul j a fost conectat cu directia i.
int delta[MAX_DIR][2] = {{0, -1}, {0, 1}, {1, -1}, {-1, 1}, {1, 0}, {-1, 0}};

/** Verifica daca s-a terminat jocul. **/
int win(int pos, int r) {
    /// Cand "pos" este 0, atunci verificam norul si sudul, iar cand este 1, celelalte.
    return (touch[pos << 1][r]) && (touch[(pos << 1) + 1][r]);
}

/** Vezi ce hexagoane de pe margine atinge (u, v). **/
void near(int u, int v, int r) {
    touch[NORTH][r] = (u == 1);
    touch[SOUTH][r] = (u == N);
    touch[EAST][r] = (v == 1);
    touch[WEST][r] = (v == N);
}

/** Gaseste radacina nodului "u". **/
int find(int u) {
    for (; boss[u]; u = boss[u]) {
        stack[ss++] = u;
    }
    int root = u;
    while (ss) {
        boss[stack[--ss]] = root;
    }
    return root;
}

/** Reuneste multimea lui "u" cu a lui "v". **/
void unify(int u, int v) {
    int i;
    if (u != v) {
        boss[v] = u;
        for (i = 0; i < MAX_COORD; i++) {
            touch[i][u] = touch[i][v] = (touch[i][u] | touch[i][v]);
        }
    }
}

int main(void) {
    int j, u, v;
    FILE *f = fopen("hex.in", "r");
    
    fscanf(f, "%d", &N);
    int i = 0, ru = 0, M = N * N;
    /// Citeste mutarile pana ce nordul si sudul sau estul si vestul sunt conectati.
    while ((i <= M) && (!win(i & 1, ru))) {
        fscanf(f, "%d %d", &u, &v);
        /// Gaseste radacina lui (u, v).
        ru = find(INDEX(u, v));
        /// Vezi ce hexagoane de pe margine atinge.
        near(u, v, ru);
        /// Uita-te prin vecini si conecteaza-te de cei cu aceeasi culoare.
        board[u][v] = round[++i & 1];
        for (j = 0; j < MAX_DIR; j++) {
            int u0 = u + delta[j][0];
            int v0 = v + delta[j][1];
            if (board[u0][v0] == board[u][v]) {
                unify(ru, find(INDEX(u0, v0)));
            }
        }
    }
    fclose(f);
    
    f = fopen("hex.out", "w");
    
    fprintf(f, "%d\n", i);
    fclose(f);
    
    /// Multumim Doamne!
    puts("Doamne ajuta!");
    return 0;
}