# HackerEarth Grid of Many Xors problem solution

In this HackerEarth Grid of Many Xors problem solution Consider a grid with N rows and M columns, where each cell has some integer value written in it. Every cell is connected to every side adjacent cell via an undirected edge. The cost of an edge e connecting any two cells with value a and b is Ce = a xor b.

We define a good trip between two cells (r1, c1) and (r2, c2) as a trip starting at cell (r1, c1) and ending at cell (r2, c2) while visiting every cell of the grid at least once.

There is a cost associated with every good trip. Let's say, for a given edge e, you travel that edge Te times. Then the cost of the trip is:
Summation(for all e) (Ce * Ceil(Te/2))

For the given starting cell (r1, c1) and ending cell (r2, c2), you have to find the minimum cost of a good trip.

## HackerEarth Grid of Many Xors problem solution.

`#include <bits/stdc++.h>using namespace std;struct dsu {  vector<int> Rank, P;  int V;  dsu(int v = 0) : V(v) {    Rank = vector<int>(v + 1, 0);    P = vector<int>(v + 1, 0);    for(int i = 0; i < P.size(); i++) {      P[i] = i, Rank[i] = 1;    }  }  int find_root(int x) { return x == P[x] ? x : P[x] = find_root(P[x]); }  void merge(int x, int y) {    int xr = find_root(P[x]), yr = find_root(P[y]);    if(xr == yr) return ;    if(Rank[xr] < Rank[yr]) swap(xr, yr), swap(x, y);    Rank[xr] += Rank[yr];    P[yr] = xr;  }};int main() {  ios_base::sync_with_stdio(false);  int t, n, m, r1, c1, r2, c2;  cin >> t;  while(t--) {    cin >> n >> m;    cin >> r1 >> c1 >> r2 >> c2;    vector<vector<int> > grid(n, vector<int>(m, 0));    for(int i = 0; i < n; i++) {      for(int j = 0; j < m; j++) {        cin >> grid[i][j];      }    }    vector<pair<int, pair<int, int> > > edges;    auto encode = [&](int r, int c) -> int {      return r * m + c;    };    for(int i = 0; i < n; i++) {      for(int j = 0; j < m; j++) {        if(j + 1 != m)          edges.push_back({grid[i][j] ^ grid[i][j + 1],                          {encode(i, j), encode(i, j + 1)}});        if(i + 1 != n)          edges.push_back({grid[i][j] ^ grid[i + 1][j],                          {encode(i, j), encode(i + 1, j)}});      }    }    sort(edges.begin(), edges.end());    dsu tester(n*m);    long long res = 0;    for(int i = 0; i < edges.size(); i++) {      int wt = edges[i].first, a = edges[i].second.first, b = edges[i].second.second;      if(tester.find_root(a) != tester.find_root(b)) {        res += wt;        tester.merge(a, b);      }    }    cout << res << '\n';  }  return 0;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;#define pi pair<int, int>#define f first#define s second#define rep(i, N) for(int i=0;i<N;i++)int pa[100011];int sz[100011];int f(int x) {    if(x == pa[x]) return x;    return pa[x] = f(pa[x]);}bool join(int a, int b) {    a = f(a);    b = f(b);    if(a != b) {        if(sz[a] < sz[b]) swap(a, b);        pa[b] = a;        sz[a] += sz[b];        return 1;    }    return 0;}struct Edge{    int u,v,val;};bool func(Edge a, Edge b) {    return a.val < b.val;}int main(){    ios_base::sync_with_stdio(0);    cin.tie(0);    int T;    cin >> T;    while(T--) {        int N,M;        cin >> N >> M;        vector<vector<int> >G(N, vector<int>(M));        int r1,c1,r2,c2;        cin >> r1 >> c1 >> r2 >> c2;        // No need for r1 c1 r2 c2. The value of answer is independent of them.        map<pi, int> C;        int cnt = 0;        vector<Edge> E;        rep(i, N) {            rep(j, M) {                cin >> G[i][j];                C[{i,j}] = cnt++;                if(i-1 >= 0) {                    E.push_back({C[{i-1,j}], C[{i,j}], G[i][j]^G[i-1][j] });                }                if(j-1 >= 0) {                    E.push_back({C[{i,j-1}], C[{i,j}], G[i][j]^G[i][j-1] });                }            }        }        sort(E.begin(),E.end(),func);        for(int j=0;j<cnt;j++) {            pa[j] = j;            sz[j] = 1;        }        int ans = 0;        for(auto e:E) {            if(join(e.u,e.v)) ans += e.val;        }        cout << ans << "\n";    }}`