Cod sursă (job #316829)

#include <iostream>
#include <stdio.h>

using namespace std;

const int N = 505 ;
const int POW = 1e3 ;



int noMoves , lin , col ;

int mat [ N ][ N ] ;
int tat [ N ][ N ] ;

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



int findTat ( int x ){
    static int l , c , ltemp , ctemp , lcpy , ccpy  ;

    l = x / POW ;
    c = x % POW ;
    lcpy = l ;
    ccpy = c ;

    while ( tat [ l ][ c ] > 0  ){
        ltemp = l ;
        ctemp = c ;

        l = tat [ ltemp ][ ctemp ]/POW ;
        c = tat [ ltemp ][ ctemp ]%POW ;
    }

    while ( tat [ lcpy ][ ccpy ] > 0 ){
        ltemp = lcpy ;
        ctemp = ccpy ;

        lcpy = tat [ ltemp ][ ctemp ]/POW ;
        ccpy = tat [ ltemp ][ ctemp ]%POW ;

        tat[ ltemp ][ ctemp ] = l *POW +c ;

    }


    return l * POW + c ;
}

void mrgTat( int x , int y ){
    static int tatx , taty , xl , xc , yl , yc ;

    tatx = findTat( x );
    taty = findTat( y );


    if ( tatx == taty ){
        return ;
    }

    xl = tatx / POW ;
    xc = tatx % POW ;
    yl = taty / POW ;
    yc = taty % POW ;


    // unim x la y
    if ( -tat [ xl ][ xc ] > -tat [ yl ][ yc ] ){
        swap( xl , yl );
        swap( xc , yc );
        swap( tatx , taty );
    }

    tat[ yl ][ yc ] += tat [ xl ][ xc ];
    tat [ xl ][ xc ] = taty ;

}


int main(){
    int i , l , c , k ;

    freopen("hex.in","r",stdin);
    freopen("hex.out","w",stdout);

    scanf("%d",&lin);
    col = lin ;
    noMoves = lin * col ;


    for ( i = 0 ; i <= lin + 1 ; i++ ){
        for ( int j = 0 ; j <= col + 1 ; j++ ){
            tat [ i ][ j ] = -1;
        }
    }

    for ( i = 0 ; i <= lin  ; i++ ){
        if ( i > 1 ){
            mrgTat( i , i - 1 );
            mrgTat( (lin + 1)*POW + i , (lin + 1)*POW + i - 1 );

            mrgTat( i * POW , ( i - 1 )*POW );
            mrgTat( i * POW + col + 1 , ( i - 1 )*POW  + col + 1 );

        }
        mat [ 0 ][ i ] = 2 ;
        mat [ lin + 1  ][ i ] = 2  ;

        mat [ i ][ 0 ] = 1 ;
        mat [ i ][ col + 1 ] = 1  ;
    }

    for ( i = 1 ; i <= noMoves ; i++ ){
        scanf("%d %d",&l , &c );

        if ( i % 2 ){
            mat [ l ][ c ] = 1 ;
        }else {
            mat [ l ][ c ] = 2 ;
        }

        for ( k = 0 ; k < 6 ; k++ ){
            if ( mat [ l ][ c ] == mat [ l + dl [ k ] ][ c + dc[ k ] ] ){
                mrgTat ( l * POW + c , (l + dl[ k ]) * POW + c + dc[ k ] );
            }
        }
        if ( findTat(  1  ) == findTat( (lin + 1) * POW + 1 ) || findTat( 1 * POW ) == findTat( POW + col + 1  )  ){
            printf("%d",i);
            return 0 ;
        }
    }

    return 0;

}