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?

#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 100001

struct 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;
}