Cod sursă (job #501784)

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

int col[6] = {0, 1, 1, 0, -1, -1};
int row[6] = {-1, -1, 0, 1, 1, 0};

int mapa[510][510];
pair<int, int> p[510][510];
pair<int, int> min_red;
int n, i, j, curri, currj;

pair<int, int> parent(pair<int, int> x){
    int xi = x.fi;
    int xj = x.se;
    if(p[xi][xj] == x)
        return x;
    else {
        p[xi][xj] = parent(p[xi][xj]);
        return p[xi][xj];
    }
}

int main(){

    ifstream cin("hex.in");
    ofstream cout("hex.out");
    cin>>n;

    for(i = 1;i<=n;i++)
        for(j = 1;j<=n;j++)
            p[i][j] = {i, j};

    for(int pas=1;pas<=n*n;pas++){
        cin>>i>>j;
        //cout<<'\n';
        min_red = p[i][j];
        if(pas%2 == 1) {
            mapa[i][j] = 1;
            for(int k =0;k<6;k++){
                curri = i+ row[k];
                currj = j + col[k];
              //  cout<<curri<<' '<<currj<<'\n';
                if(curri > 0 && curri <= n && currj > 0 && currj <= n) {
                    if(mapa[curri][currj] == 1)
                        if(min_red.se > p[curri][currj].se){
                            min_red = p[curri][currj];
                        }
                }
            }
            //cout<<'\n';
            //cout<<min_red.fi<<' '<<min_red.se<<'\n';
            //cout<<'\n';
            p[parent({i, j}).fi][parent({i, j}).se] = parent(min_red);
            for(int k =0;k<6;k++){
                curri = i+ row[k];
                currj = j + col[k];
                if(mapa[curri][currj] == 1)
                    p[parent({curri, currj}).fi][parent({curri, currj}).se] = parent(min_red);
            }

            if(j == n && p[i][j].se == 1){
                cout<<pas;
                return 0;
            }
        }
        else {
            mapa[i][j] = 2;
            for(int k =0;k<6;k++){
                curri = i+ row[k];
                currj = j + col[k];
          //      cout<<curri<<' '<<currj<<'\n';
                if(curri > 0 && curri <= n && currj > 0 && currj <= n) {
                    if(mapa[curri][currj] == 2)
                        if(min_red.fi > p[curri][currj].fi){
                            min_red = p[curri][currj];
                        }
                }
            }
            //cout<<'\n';
            //cout<<min_red.fi<<' '<<min_red.se<<'\n';
            p[parent({i, j}).fi][parent({i, j}).se] = parent(min_red);
            //cout<<'\n';
            for(int k =0;k<6;k++){
                curri = i+ row[k];
                currj = j + col[k];
                if(mapa[curri][currj] == 2)
                    p[parent({curri, currj}).fi][parent({curri, currj}).se] = parent(min_red);
            }

            if(i == n && p[i][j].fi == 1){
                cout<<pas;
                return 0;
            }
        }
    }
   /* for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cout<<mapa[i][j]<<' ';
        cout<<'\n';
    }
    cout<<'\n';
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cout<<p[i][j].fi<<p[i][j].se<<' ';
        cout<<'\n';
    }
*/
    return 0;
}