HackerEarth Covering Chessboard problem solution

In this HackerEarth Covering Chessboard problem solution You have an n by m grid. Each grid square has a certain value associated with it. This is given by the numbers vi,j.

You can capture grid squares in two different ways.

1. You can directly capture a grid square. This costs ci,j.
2. You can indirectly capture a grid square. You can only do this if we have already captured all of this squares neighbors. This costs bi,j ≤ ci,j.

Two squares are neighbors if they share an edge.

Your score is the sum of values you have captured minus the cost it took to capture those squares. Return the maximum possible score you can achieve.

HackerEarth Covering Chessboard problem solution.

import java.util.Arrays;
import java.util.Scanner;

public class CoveringChessboard {
  public static int[] dx = {-1,0,1,0}, dy = {0,1,0,-1};
  public static void main (String[] args) {
    Scanner in = new Scanner(System.in);
    n = in.nextInt();
    m = in.nextInt();
    int[][] v = new int[n][m];
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) v[i][j] = in.nextInt();
    int[][] b = new int[n][m];
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) b[i][j] = in.nextInt();
    int[][] c = new int[n][m];
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) c[i][j] = in.nextInt();
    
    init(n*m*2+2, n*m*4*2+n*m*4*2);
    long all = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        all += v[i][j];
        int nn = getNum(i,j);
        if ((i+j) % 2 == 0) {
          for (int k = 0; k < 4; k++) {
            int nx = i+dx[k], ny = j+dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            int dn = getNum(nx,ny);
            add_edge(nn*2, dn*2, INF);
            add_edge(nn*2+1, dn*2+1, INF);
          }
          add_edge(nn*2+1, N-2, Math.min(b[i][j], v[i][j]));
          add_edge(N-1, nn*2, c[i][j]);
          add_edge(nn*2+1, nn*2, INF);
          add_edge(nn*2, nn*2+1, v[i][j]);
        } else {
          add_edge(nn*2+1, N-2, c[i][j]);
          add_edge(N-1, nn*2, Math.min(b[i][j], v[i][j]));
          add_edge(nn*2+1, nn*2, INF);
          add_edge(nn*2, nn*2+1, v[i][j]);
        }
      }
    }
    
    System.out.println(all-dinic(N-1, N-2));
    System.exit(0);
  }
  public static int n,m;
  public static int getNum(int i, int j) {
    return i*m+j;
  }
  
  public static int N;
  public static int INF = 1 << 29;
  public static int[] eadj, eprev, elast, now;
  public static int eidx;
  private static long[] flow, capa;

  public static void init(int _N, int M) {
    N = _N;
    eadj = new int[M];
    eprev = new int[M];
    elast = new int[N];
    flow = new long[M];
    capa = new long[M];
    now = new int[N];
    level = new int[N];
    eidx = 0;
    Arrays.fill(elast, -1);
  }

  private static void add_edge(int a, int b, int c) {
    eadj[eidx] = b; flow[eidx] = 0; capa[eidx] = c; eprev[eidx] = elast[a]; elast[a] = eidx++;
    eadj[eidx] = a; flow[eidx] = c; capa[eidx] = c; eprev[eidx] = elast[b]; elast[b] = eidx++;
  }

  private static long dinic(int source, int sink) {
    long res, flow = 0;
    while (bfs(source, sink)) { // see if there is an augmenting path
      System.arraycopy(elast, 0, now, 0, N);
      while ((res = dfs(source, INF, sink)) > 0)
        // push all possible flow through
        flow += res;
    }
    return flow;
  }

  private static int[] level;

  private static boolean bfs(int source, int sink) {
    Arrays.fill(level, -1);
    int front = 0, back = 0;
    int[] queue = new int[N];
    level[source] = 0;
    queue[back++] = source;
    while (front < back && level[sink] == -1) {
      int node = queue[front++];
      for (int e = elast[node]; e != -1; e = eprev[e]) {
        int to = eadj[e];
        if (level[to] == -1 && flow[e] < capa[e]) {
          level[to] = level[node] + 1;
          queue[back++] = to;
        }
      }
    }

    return level[sink] != -1;
  }

  private static long dfs(int cur, long curflow, int goal) {
    if (cur == goal)
      return curflow;

    for (int e = now[cur]; e != -1; now[cur] = e = eprev[e]) {
      if (level[eadj[e]] > level[cur] && flow[e] < capa[e]) {
        long res = dfs(eadj[e], Math.min(curflow, capa[e] - flow[e]), goal);
        if (res > 0) {
          flow[e] += res;
          flow[e ^ 1] -= res;
          return res;
        }
      }
    }
    return 0;
  }
}

Second solution

#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int N = 4031;

int d[N];
int ptr[N];

struct edge
{
  int a, b, cap, flow;
};

vector<edge> e;
vector<int> g[N];
int s, t;
int n, m;
int c[50][50], v[50][50], b[50][50];

void add_edge(int a, int b, int cap)
{
  edge e1 = { a, b, cap, 0 };
  g[a].push_back(e.size());
  e.push_back(e1);
  edge e2 = { b, a, 0, 0 };
  g[b].push_back(e.size());
  e.push_back(e2);
}

int bfs()
{
  for (int i = 0; i < N; i++)
  {
    d[i] = -1;
  }
  queue<int> qu;
  qu.push(s);
  d[s] = 0;
  while (qu.size())
  {
    int v = qu.front();
    qu.pop();
    for (int i = 0; i < g[v].size(); i++)
    {
      int id = g[v][i];
      int to = e[id].b;
      if (e[id].flow == e[id].cap)
        continue;
      if (d[to] != -1)
        continue;
      d[to] = d[v] + 1;
      qu.push(to);
    }
  }
  return (d[t] != -1);
}

int dfs(int v, int flow)
{
  if (v == t || flow == 0)
    return flow;
  for (; ptr[v] < g[v].size(); ptr[v]++)
  {
    int id = g[v][ptr[v]];
    int to = e[id].b;
    if (d[to] != d[v] + 1)
      continue;
    int pushed = dfs(to, min(flow, e[id].cap - e[id].flow));
    if (pushed)
    {
      e[id].flow += pushed;
      e[id ^ 1].flow -= pushed;
      return pushed;
    }
  }
  return 0;
}

int dinic()
{
  int flow = 0;
  while (true)
  {
    if (!bfs())
      break;
    for (int i = 0; i < N; i++)
      ptr[i] = 0;
    while (true)
    {
      int pushed = dfs(s, 100000000);
      if (pushed == 0)
        break;
      flow += pushed;
    }
  }
  return flow;
}

int get_ps(int a, int b)
{
  return a*m + b;
}

int paired(int x)
{
  if (x >= 1000)
    return x - 1000;
  return x + 1000;
}

bool outside(int a, int b)
{
  return (a < 0 || a >= n || b < 0 || b >= m);
}

int main(){
  ios_base::sync_with_stdio(0);

  cin >> n >> m;

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cin >> v[i][j];
    }
  }
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cin >> b[i][j];
    }
  }
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cin >> c[i][j];
    }
  }

  int can_get = 0;

  s = N - 2;
  t = N - 1;

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      can_get += v[i][j];

      int ps = get_ps(i, j);

      add_edge(ps, paired(ps), v[i][j]);

      if (i % 2 != j % 2)
      {
        add_edge(s, ps, c[i][j]);
        add_edge(paired(ps), t, min(b[i][j], v[i][j]));
        for (int di = -1; di <= 1; di++)
        {
          for (int dj = -1; dj <= 1; dj++)
          {
            if (abs(di) + abs(dj) != 1)
              continue;
            if (outside(i + di, j + dj))
              continue;
            int V = get_ps(i + di, j + dj);
            add_edge(ps, V, INF);
            add_edge(paired(ps), paired(V),INF);

          }
        }
      }
      else
      {
        add_edge(s, ps, min(b[i][j], v[i][j]));
        add_edge(paired(ps), t, c[i][j]);
      }

    }
  }

  cout << can_get - dinic() << endl;

  return 0;
}