Cod sursă (job #80760)

//Pentru simplitate consideram 4 noduri suplimentare
//sus,jos,stanga,dreapta
//toate sunt puncte extreme
//daca sus si jos sunt in aceeasi multime sau stanga dreapta sunt in aceeasi multime
//problema s-a terminat

#include <cstdio>
using namespace std;

FILE *in=fopen("hex.in","r");
FILE *out=fopen("hex.out","w");

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

int n;
char st[N + 1][N + 1];

struct punct{
    short int x;
    short int y;
}d[N][N];

punct rad (short int x, short int y)
{
    punct r;
    if(d[x][y].x==0 && d[x][y].y==0){
        r.x=x;
        r.y=y;
        return r;
    }
    r=rad(d[x][y].x,d[x][y].y);
    d[x][y]=r;
    return r;
}

inline bool petabla (int x, int y)
{
    if(x<1 || x>n) return 0;
    if(y<1 || y>n) return 0;
    return 1;
}

int main()
{
    int i,j;
    punct r1,r2;
    bool ok=0;

    fscanf(in,"%d",&n);
    for(i = 0 ; i <= n ; i++)
        for(j = 0 ; j <= n ; j++ )   d[i][j].x=d[i][j].y=0;

    i=1;
    int xc,yc,x,y,s;
    while(i<=n*n && !ok){
        fscanf(in,"%d%d",&x,&y);

        //0 - neocupat
        //1 - rosu
        //2 - albastru
        s=i%2==1?1:2;

        st[x][y]=s;
        r1=rad(x,y);
        for(j = 0 ; j < 6 ; j++){
            xc=x+dx[j];
            yc=y+dy[j];
            if(petabla(xc,yc) && st[xc][yc]==s){
                r2=rad(xc,yc);
                if(r1.x!=r2.x || r1.y!=r2.y)
                    d[r2.x][r2.y]=r1;
            }
        }

        if(s==1){
            if(y==1){
                r2=rad(1,0);
                if(r1.x!=r2.x || r1.y!=r2.y){
                    d[r1.x][r1.y].x=r2.x;
                    d[r1.x][r1.y].y=r2.y;
                }
            }
            if(y==n){
                r2=rad(2,0);
                if(r1.x!=r2.x || r1.y!=r2.y){
                    d[r1.x][r1.y].x=r2.x;
                    d[r1.x][r1.y].y=r2.y;
                }
            }
            if(rad(1,0).x == rad(2,0).x && rad(1,0).y == rad(2,0).y)
                ok=1;
        }
        if(s==2){
            if(x==1){
                r2=rad(0,1);
                if(r1.x!=r2.x || r1.y!=r2.y){
                    d[r1.x][r1.y].x=r2.x;
                    d[r1.x][r1.y].y=r2.y;
                }
            }
            if(x==n){
                r2=rad(0,2);
                if(r1.x!=r2.x || r1.y!=r2.y){
                    d[r1.x][r1.y].x=r2.x;
                    d[r1.x][r1.y].y=r2.y;
                }
            }
            if(rad(0,1).x == rad(0,2).x && rad(0,1).y == rad(0,2).y)
                ok=1;
        }
        i++;
    }

    fprintf(out,"%d",i-1);
    return 0;
}