Cod sursă (job #194932)

#include <iostream>
#include <fstream>
#include <utility>
#define x first
#define y second
#define NMAX 505
using namespace std;

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

pair<int,int> t[NMAX][NMAX],rad1,rad2;
int a[NMAX][NMAX];
pair<int,int> sus,jos,stanga,dreapta;
int xx,yy;
int l,c,n,nr,r[NMAX][NMAX];
const int dx[]={-1,-1,0,0,1,1};
const int dy[]={0,1,-1,1,-1,0};

bool egal(pair<int,int> a,pair<int,int> b)
{
    if(a.x == b.x && a.y == b.y)
        return true;
    return false;
}

void init()
{
    for(int i=1;i<=n;i++)
    {
        t[1][i] = sus;
        t[i][1] = stanga;
        t[n][i] = jos;
        t[i][n] = dreapta;
    }

}

pair<int,int> Find(pair<int,int> x)
{
    pair<int,int> r,aux;
    for(r=x;r!=t[r.x][r.y];r= t[r.x][r.y]);

    for(pair<int,int> i=x;i!=r;)
    {
        aux = t[i.x][i.y];
        t[i.x][i.y]= r;
        i = aux;
    }
    return r;
}

void Union(pair<int,int> r1,pair<int,int> r2)
{
    if(r[r1.x][r1.y]>r[r2.x][r2.y])
    {
        t[r2.x][r2.y] = r1;
    }
    else
        t[r1.x][r1.y] = r2;

    if(r[r1.x][r1.y]==r[r2.x][r2.y])
    {
        r[r2.x][r2.y]++;
    }

}

void afisare()
{
     for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout << "(" << t[i][j].x <<"," << t[i][j].y << ")" << " ";
        }
        cout << endl;
    }
    cout << endl << endl;
}

int main()
{
    in >> n;
    sus = make_pair(0,1);
    jos = make_pair(n+1,1);
    stanga = make_pair(1,0);
    dreapta = make_pair(1,n+1);
    t[0][1] = sus;
    t[n+1][1] = jos;
    t[1][0] = stanga;
    t[1][n+1] = dreapta;
    init();
    for(int i=1;i<=n*n;i++)
    {
        in >> l >> c;
        //afisare();
        if(i%2==1)
            a[l][c] =1;
        else
            a[l][c] =2;
        if(t[l][c].x==0 && t[l][c].y==0)
            t[l][c] = make_pair(l,c);

        for(int k=0;k<8;k++)
        {
            xx = l + dx[k];
            yy = c + dy[k];
            if(xx>0 && xx<=n && yy>0 && yy<=n && a[xx][yy] !=0 && a[xx][yy]==a[l][c])
            {
                rad2 = Find(make_pair(xx,yy));
                rad1 = Find(t[l][c]);
                if(rad1!=rad2)
                    Union(rad1,rad2);
            }
        }
        if(Find(stanga)==Find(dreapta))
        {
            nr = i;
            break;
        }
        if(Find(sus) == Find(jos))
        {
            nr = i;
            break;
        }
    }
    out << nr;

    return 0;
}