# HackerEarth Puzzled Grid problem solution

In this HackerEarth Puzzled Grid problem solution Today, you need to solve a problem on a Puzzled Grid game. "In a grid of n x n size, where each cell has a positive integer, two players compete in several rounds.

Each round starts by both players putting a rock in a random location of the grid. Then, the two players must connect the two rocks with a line that passes through the grid cells (e.g: from a grid cell the line can can expand either horizontally or vertically and never out the grid). Since there may be a lot of ways to connect the two stones, we are only interested in those lines that minimizes the highest cell in their path (e.g: the cell with the highest number should be as small as possible).

You need to find and print this minimized maximum. Can you do it?

## HackerEarth Puzzled Grid problem solution.

`#include <stdio.h>#include <vector>#include <algorithm>#include <map>#include <set>#define maxn 3000using namespace std;int p[maxn*maxn];int sizeOf[maxn*maxn];int get( int x ) {    if( p[x] != x ) {        p[x] = get(p[x]);    }    return p[x];}void Union( int x, int y ) {    x = get(x), y = get(y);        if( x != y ) {        if( sizeOf[x] < sizeOf[y] ) {            swap(x, y);        }                p[y] = x;        sizeOf[x] += sizeOf[y];    }}void init( int n ) {    for( int i = 0; i < n; i++ ) {        p[i] = i;        sizeOf[i] = 1;    }}int grid[maxn][maxn];vector<pair<int,int>> cells[1000001];vector<int> s[1000001];int main( void ) {    int n, q;    scanf("%i %i", &n, &q);        const int max_num = 1000000;        for( int i = 0; i < n; i++ ) {        for( int j = 0; j < n; j++ ) {            scanf("%i", &grid[i][j]);            cells[grid[i][j]].push_back(make_pair(i,j));        }    }            vector<int> X1(q), Y1(q), X2(q), Y2(q);    vector<int> lo(q), hi(q), ans(q);        for( int i = 0; i < q; i++ ) {        scanf("%i %i %i %i", &X1[i], &Y1[i], &X2[i], &Y2[i]);        lo[i] = 1, hi[i] = int(1e6)+1;    }        int lg = 21;    while( lg-- ) {         for( int i = 0; i < q; i++ ) {            if( lo[i] <= hi[i] ) {                int mid = (lo[i] + hi[i]) / 2;                s[mid].push_back(i);            }        }                init(n*n);                for( int e = 1; e <= max_num; e++ ) {            if( !cells[e].empty() ) {                for( auto cell : cells[e] ) {                    int dx[] = {0, 0, +1, -1};                    int dy[] = {+1, -1, 0, 0};                                        int x = cell.first, y = cell.second;                    for( int c = 0; c < 4; c++ ) {                        int nx = x + dx[c], ny = y + dy[c];                                                if( (nx >= 0) && (nx < n) && (ny >= 0) && (ny < n) ) {                            if( grid[nx][ny] <= grid[x][y] ) {                                int cellId0 = (x * n) + y;                                int cellId1 = (nx * n) + ny;                                Union(cellId0, cellId1);                            }                        }                    }                }            }                        if( !s[e].empty() ) {                for( int idx : s[e] ) {                    int cellId0 = (X1[idx] * n) + Y1[idx];                    int cellId1 = (X2[idx] * n) + Y2[idx];                                        if( get(cellId0) == get(cellId1) ) {                        ans[idx] = e;                        hi[idx] = e - 1;                    } else {                        lo[idx] = e + 1;                    }                }            }        }                for( int i = 1; i <= max_num; i++ ) {            s[i].clear();        }    }        for( int i = 0; i < q; i++ ) {        printf("%i\n", ans[i]);    }        return 0;}`

### Second solution

`#include <fstream>#include <iostream>#include <string>#include <complex>#include <math.h>#include <set>#include <vector>#include <map>#include <queue>#include <stdio.h>#include <stack>#include <algorithm>#include <list>#include <ctime>#include <memory.h>#include <assert.h>#define y0 sdkfaslhagaklsldk#define y1 aasdfasdfasdf#define yn askfhwqriuperikldjk#define j1 assdgsdgasghsf#define tm sdfjahlfasfh#define lr asgasgash#define norm asdfasdgasdgsd#define have adsgagshdshfhds#define eps 1e-6#define M_PI 3.141592653589793#define bs 1000000007#define bsize 350using namespace std;const int INF = 1e9;const int N = 531;const int M = 600031;int n, m, ar[N][N];int x1[M], y1[M], x2[M], y2[M];vector<pair<int, pair<int, int> > > val_list;int l[M], r[M];vector<int> qu_list[M];int w[M];int get(int x){    if (x == w[x])        return x;    return w[x] = get(w[x]);}bool outside(int a, int b){    if (a < 0 || a >= n || b < 0 || b >= n)        return true;    return false;}void merge(int a, int b){    w[a] = b;}bool is_inside(int a, int b){    return (a >=0 && a < n&&b >= 0 && b < n);}void run_merger(int a, int b){    for (int dx = -1; dx <= 1; dx++)    {        for (int dy = -1; dy <= 1; dy++)        {            if (abs(dx) + abs(dy) != 1)                continue;            if (outside(a + dx, b + dy))                continue;            if (ar[a + dx][b + dy] > ar[a][b])                continue;            int id1 = a*n + b;            int id2 = (a + dx)*n + (b + dy);            id1 = get(id1);            id2 = get(id2);            merge(id1, id2);        }    }}int main(){    ios_base::sync_with_stdio(0);    //cin.tie(0);    //cin >> n >> m;    assert(cin >> n >> m);    assert(2 <= n &&n <= 500);    assert(m >= 1 && m <= 1e5);    for (int i = 1; i <= n; i++)    {        for (int j = 1; j <= n; j++)        {            //cin >> ar[i - 1][j - 1];            assert(cin >> ar[i - 1][j - 1]);            assert(ar[i - 1][j - 1] >= 1 && ar[i - 1][j - 1] <= 1e6);        }    }    for (int i = 1; i <= m; i++)    {//      cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];        assert(cin >> x1[i] >> y1[i] >> x2[i] >> y2[i]);        assert(x1[i] != x2[i] || y1[i] != y2[i]);        assert(is_inside(x1[i], y1[i]));        assert(is_inside(x2[i], y2[i]));    }    for (int i = 1; i <= n; i++)    {        for (int j = 1; j <= n; j++)        {            val_list.push_back(make_pair(ar[i - 1][j - 1], make_pair(i - 1, j - 1)));        }    }    sort(val_list.begin(), val_list.end());    for (int i = 1; i <= m; i++)    {        l[i] = 0;        r[i] = val_list.size() - 1;    }    int I = 0;    while (true)    {        for (int i = 0; i < val_list.size(); i++)            qu_list[i].clear();        int flag = 0;        for (int i = 1; i <= m; i++)        {            if (l[i] == r[i])                continue;            flag = 1;            int mid = l[i] + r[i];            mid /= 2;            qu_list[mid].push_back(i);        }        ++I;        if (flag == 0)            break;        for (int i = 0; i < n; i++)        {            for (int j = 0; j < n; j++)            {                w[i*n + j] = i*n + j;            }        }        for (int i = 0; i < val_list.size(); i++)        {            int qi = val_list[i].second.first;            int qj = val_list[i].second.second;            run_merger(qi, qj);            for (int j = 0; j < qu_list[i].size(); j++)            {                int id = qu_list[i][j];                int ps1 = x1[id] * n + y1[id];                int ps2 = x2[id] * n + y2[id];                //  cout << ps1 << "%" << ps2 << endl;                ps1 = get(ps1);                ps2 = get(ps2);                //              cout << id << "%" << i << endl;                if (ps1 == ps2)                    r[id] = i;                else                    l[id] = i + 1;            }        }    }    for (int i = 1; i <= m; i++)    {        cout << val_list[l[i]].first << endl;    }    cin.get(); cin.get();    return 0;}`