Cod sursă (job #503100)

#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};
char mapa[510][510];
pair<short int, short int> pmax[510][510];
pair<short int,short int> pmin[510][510];
int n, i, j, curri, currj;

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

pair<short int, short int> parent_max(pair<short int, short int> x){
    short int xi = x.fi;
    short int xj = x.se;
    if(pmax[xi][xj] == x)
        return x;
    else {
        pmax[xi][xj] = parent_max(pmin[xi][xj]);
        return pmax[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++){
            pmax[i][j] = {i, j};
            pmin[i][j] = {i, j};
        }

    for(int pas=1;pas<=n*n;pas++){
        cin>>i>>j;
        //cout<<'\n';

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

                        if(parent_max({curri, currj}) > parent_max({i, j})) {
                            pmax[parent_max({i,j}).fi][parent_max({i,j}).se] = parent_max({curri, currj});
                        }
                        else pmax[parent_max({curri, currj}).fi][parent_max({curri, currj}).se] = parent_max({i, j});
                    }
                }


            }
            if(pmax[i][j].se == n && pmin[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];
               // max_grup[i][j] = max(max_grup[i][j]);
              //  cout<<curri<<' '<<currj<<'\n';
                if(curri > 0 && curri <= n && currj > 0 && currj <= n) {
                    if(mapa[curri][currj] == 2){
                        if(parent_min({curri, currj}) < parent_min({i, j})) {
                            pmin[parent_min({i,j}).fi][parent_min({i,j}).se] = parent_min({curri, currj});
                        }
                        else pmin[parent_min({curri, currj}).fi][parent_min({curri, currj}).se] = parent_min({i, j});

                        if(parent_max({curri, currj}) > parent_max({i, j})) {
                            pmax[parent_max({i,j}).fi][parent_max({i,j}).se] = parent_max({curri, currj});
                        }
                        else pmax[parent_max({curri, currj}).fi][parent_max({curri, currj}).se] = parent_max({i, j});
                    }
                }


            }
            if(pmax[i][j].fi == n && pmin[i][j].fi == 1){
                cout<<pas;
                return 0;
            }

        }
    }


    return 0;
}