Cod sursă (job #194904)

#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;
bool a[NMAX][NMAX];
pair<int,int> sus,jos,stanga,dreapta;
int xx,yy;
int l,c,n,nr,r[NMAX][NMAX];
int dx[] = {0,0,1,-1};
int dy[] = {-1,1,0,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]++;
    }

}

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;
        a[l][c] = true;
        if(t[l][c].x==0 && t[l][c].y==0)
            t[l][c] = make_pair(l,c);

        for(int k=0;k<4;k++)
        {
            xx = l + dx[k];
            yy = c + dy[k];
            if(xx>0 && xx<=n && yy>0 && yy<=n && a[xx][yy] ==true)
            {
                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+1;

    return 0;
}