# HackerEarth Shubham and Grid problem solution

In this HackerEarth Shubham and Grid problem solution You are given a grid of n rows and m columns consisting of lowercase English letters a, b, c, and d.

We say 4 cells form a "nice-quadruple" if and only if
1. The letters on these cells form a permutation of the set {a,b,c,d}.
2. The cell marked b is directly reachable from cell marked a.
3. The cell marked c is directly reachable from the cell marked b.
4. The cell marked d is directly reachable from the cell marked c.
A cell (x2,y2) is said to be directly reachable from cell (x1,y1) if and only if (x2,y2) is one of these 4 cells { (x1 -1,y1), (x1+1,y1), (x1,y1-1) and (x1,y1+1)}).

Given the constraint that each cell can be part of at most 1 "nice-quadruple", what's the maximum number of "nice-quadruples" you can select?

## HackerEarth Shubham and Grid problem solution.

`#include <iostream>#include<bits/stdc++.h>using namespace std;#define ll long long int#define inf 1000000000000#define mod 1000000007#define pb push_back#define mp make_pair#define all(v) v.begin(),v.end()#define S second#define F first#define boost1 ios::sync_with_stdio(false);#define boost2 cin.tie(0);#define mem(a,val) memset(a,val,sizeof a)#define endl "\n"#define maxn 100001struct Edge {  ll from, to, cap, flow, index;  Edge(ll from, ll to, ll cap, ll flow, ll index) :  from(from), to(to), cap(cap), flow(flow), index(index) {}};struct PushRelabel{  ll N;  vector<vector<Edge> > G;  vector<ll> excess;  vector<ll> dist, active, count;  queue<int> Q;  PushRelabel(ll N) : N(N), G(N), excess(N), dist(N), active(N), count(2*N) {}  void AddEdge(ll from, ll to, ll cap) {    G[from].push_back(Edge(from, to, cap, 0, G[to].size()));    if (from == to) G[from].back().index++;    G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));  }  void Enqueue(ll v) {    if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); }  }  void Push(Edge &e) {    ll amt=min(excess[e.from], e.cap - e.flow);    if (dist[e.from] <= dist[e.to] || amt == 0) return;    e.flow += amt;    G[e.to][e.index].flow -= amt;    excess[e.to] += amt;    excess[e.from] -= amt;    Enqueue(e.to);  }  void Gap(ll k) {    for (ll v = 0; v < N; v++) {      if (dist[v] < k) continue;      count[dist[v]]--;      dist[v] = max(dist[v], N+1);      count[dist[v]]++;      Enqueue(v);    }  }  void Relabel(ll v) {    count[dist[v]]--;    dist[v] = 2*N;    for (ll i = 0; i < G[v].size(); i++)      if (G[v][i].cap - G[v][i].flow > 0)  dist[v] = min(dist[v], dist[G[v][i].to] + 1);    count[dist[v]]++;    Enqueue(v);  }  void Discharge(ll v) {    for (ll i = 0; excess[v] > 0 && i < G[v].size(); i++) Push(G[v][i]);    if (excess[v] > 0) {      if (count[dist[v]] == 1)  Gap(dist[v]);      else  Relabel(v);    }  }  ll GetMaxFlow(ll s, ll t) {    count[0] = N-1;    count[N] = 1;    dist[s] = N;    active[s] = active[t] = true;    for (ll i = 0; i < G[s].size(); i++) {      excess[s] += G[s][i].cap;      Push(G[s][i]);    }    while (!Q.empty()) {      int v = Q.front();      Q.pop();      active[v] = false;      Discharge(v);    }    ll totflow = 0;    for (ll i = 0; i < G[s].size(); i++) totflow += G[s][i].flow;    return totflow;  }  vector<vector<Edge> > build(){  return G;  }};int id[25][25],n,m;char arr[25][25];int di[]={1,-1,0,0};int dj[]={0,0,1,-1};int valid(int x,int y){  return (x>=1 && x<=n && y>=1 && y<=m);}int main(){  boost1;boost2;  int i,j,x,y,ctr=0,src,sink,ni,nj,k;  cin>>n>>m;  for(i=1;i<=n;i++)  {    for(j=1;j<=m;j++)    cin>>arr[i][j];  }  ctr=0;  for(i=1;i<=n;i++)  {    for(j=1;j<=m;j++)    {      ctr++;      id[i][j]=ctr;    }  }  PushRelabel network(2+2*n*m);  src=0;  sink=1+2*n*m;  for(i=1;i<=n;i++)  {    for(j=1;j<=m;j++)    {      if(arr[i][j]=='a')      {        network.AddEdge(src,id[i][j],1);        for(k=0;k<4;k++)        {          ni=i+di[k];          nj=j+dj[k];          if(!valid(ni,nj) || arr[ni][nj]!='b')          continue;          network.AddEdge(id[i][j],id[ni][nj],1);        }      }      else if(arr[i][j]=='b')      {        network.AddEdge(id[i][j],n*m+id[i][j],1);        for(k=0;k<4;k++)        {          ni=i+di[k];          nj=j+dj[k];          if(!valid(ni,nj) || arr[ni][nj]!='c')          continue;          network.AddEdge(n*m+id[i][j],id[ni][nj],1);        }      }      else if(arr[i][j]=='c')      {        network.AddEdge(id[i][j],n*m+id[i][j],1);        for(k=0;k<4;k++)        {          ni=i+di[k];          nj=j+dj[k];          if(!valid(ni,nj) || arr[ni][nj]!='d')          continue;          network.AddEdge(n*m+id[i][j],id[ni][nj],1);        }      }      else      network.AddEdge(id[i][j],sink,1);    }  }  cout<<network.GetMaxFlow(src,sink);  return 0;}`

### Second solution

`#include <cstdio>#include <cstring>#include <cstdlib>#include <cassert>#include <iostream>#include <algorithm>#include <vector>#include <queue>using namespace std;const int MAXN = 20;const int MAXNODE = MAXN * MAXN * 2 + 2;const int dx[4] = {1, 0, -1, 0};const int dy[4] = {0, 1, 0, -1};int n, m, source, sink;char a[MAXN][MAXN];int mark[256], x[4], y[4];vector<int> vtx, capacity, nextEdge;int head[MAXNODE];void addEdge(int a, int b){    vtx.push_back(b);    nextEdge.push_back(head[a]);    head[a] = capacity.size();    capacity.push_back(1);    vtx.push_back(a);    nextEdge.push_back(head[b]);    head[b] = capacity.size();    capacity.push_back(0);}void generate(int i){    if (i == 4) {        addEdge(source, mark['a']);        addEdge(mark['a'] + n * m, mark['b']);        addEdge(mark['b'] + n * m, mark['c']);        addEdge(mark['c'] + n * m, mark['d']);        addEdge(mark['d'] + n * m, sink);        return;    }    for (int j = i - 1; j < i; ++ j) {        for (int k = 0; k < 4; ++ k) {            int tx = x[j] + dx[k], ty = y[j] + dy[k];            if (tx >= 0 && ty >= 0 && tx < n && ty < m &&                 a[tx][ty] == 'a' + i) {                mark[a[tx][ty]] = tx * m + ty;                x[i] = tx;                y[i] = ty;                generate(i + 1);                mark[a[tx][ty]] = -1;            }        }    }}bool bfs(){    queue<int> q;    vector<int> pre(sink + 1, -1);    q.push(source);    pre[source] = -2;    while (q.size() && pre[sink] == -1) {        int u = q.front();        q.pop();        for (int p = head[u]; p != -1; p = nextEdge[p]) {            if (capacity[p]) {                int v = vtx[p];                if (pre[v] == -1) {                    pre[v] = p;                    q.push(v);                }            }        }    }    if (pre[sink] == -1) {        return false;    }    for (int u = sink, p; u != source; u = vtx[p]) {        p = pre[u];        -- capacity[p];        ++ capacity[p ^= 1];    }    return true;}int main(){    assert(scanf("%d%d", &n, &m) == 2 && 1 <= n && n <= MAXN && 1 <= m && m <= MAXN);    source = 2 * n * m;    sink = source + 1;    memset(head, -1, sizeof(head));    for (int i = 0; i < n; ++ i) {        for (int j = 0; j < m; ++ j) {            char s[10];            assert(scanf("%s", s) == 1);            assert(strlen(s) == 1);            a[i][j] = s[0];            assert('a' <= a[i][j] && a[i][j] <= 'd');            if (a[i][j] <= 'd') {                addEdge(i * m + j, i * m + j + n * m);            }        }    }    cerr << "I/O: " << capacity.size() << endl;    memset(mark, -1, sizeof(mark));    for (int i = 0; i < n; ++ i) {        for (int j = 0; j < m; ++ j) {            if (a[i][j] == 'a') {                x[0] = i;                y[0] = j;                mark['a'] = i * m + j;                generate(1);            }        }    }    cerr << "Generation done: " << capacity.size() << endl;    int flow = 0;    while (bfs()) {        ++ flow;    }    printf("%d\n", flow);    return 0;}`