HackerRank Oil Well problem solution

In this HackerRank Oil Well problem solution, The rectangular plot bought by Mr. Road Runner is divided into r * c blocks. Only some blocks are suitable for setting up the oil well and these blocks have been marked. ACME charges nothing for building the first oil well. For every subsequent oil well built, the cost would be the maximum ACME distance between the new oil well and the existing oil wells.

If (x,y) is the position of the block where a new oil well is set up and (x1, y1) is the position of the block of an existing oil well, the ACME distance is given by

max(|x-x1|, |y-y1|)

the maximum ACME distance is the maximum among all the ACME distances between existing oil wells and new wells.

If the distance of any two adjacent blocks (horizontal or vertical) is considered 1 unit, what is the minimum cost (E) in units it takes to set up oil wells across all the marked blocks?

HackerRank Oil Well problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

r, c = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
    bs = list(map(int, input().strip().split()))
    for j in range(c):
        g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
    for j in range(n):
        x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs  = g
fz  = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
    for i in range(n - d):
        I = i + d + 1
        for j in range(n-d):
            J = j + d + 1
            total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
            anz[i][j] = min(
                ans[i][j] + d * (total - fs[i][j]),
                ans[i][j + 1] + d * (total - fs[i][j + 1]),
                ans[i + 1][j] + d * (total - fs[i + 1][j]),
                ans[i + 1][j + 1] + d*(total - fs[i + 1][j + 1]))
    ans, anz = anz, ans
    fs, fz =  fz, fs
print(ans[0][0])

Oil Well problem solution in Java.

import java.io.*;
import java.math.*;
import java.util.*;

public class Solution {

  static final int MAX = 53;
  
  static int oilWell(int[][] blocks, int r, int c) {
    int[][][][] s = new int[MAX][MAX][MAX][MAX];
    for (int i = 0; i < r; i++) {
      for (int l = 0; l + i < r; l++) {
        for (int j = 0; j < c; j++) {
          for (int u = 0; u+j < c; u++) {
            int li = l + i;
            int d = u + j;

            if (l == li && u == d) {
              s[l][li][u][d] = 0;
              continue;
            }

            int h = Integer.MAX_VALUE;

            if (l < li) {
              int kl = 0, kr = 0;
              for (int x = u; x <= d; x++) {
                if (blocks[l][x] > 0) {
                  kl += fine(l, x, l+1, li, u, d);
                }

                if (blocks[li][x] > 0) {
                  kr += fine(li, x, l, li-1, u, d);
                }
              }

              h = Math.min(h, s[l+1][li][u][d] + kl);
              h = Math.min(h, s[l][li-1][u][d] + kr);
            }

            if (u < d) {
              int ku = 0;
              int kd = 0;
              for (int x = l; x <= li; x++) {
                if (blocks[x][u] > 0) {
                  ku += fine(x, u, l, li, u+1, d);
                }
                if (blocks[x][d] > 0) {
                  kd += fine(x, d, l, li, u, d-1);
                }
              }

              h = Math.min(h, s[l][li][u+1][d] + ku);
              h = Math.min(h, s[l][li][u][d-1] + kd);
            }

            s[l][li][u][d] = h;
          }
        }
      }
    }
    return s[0][r - 1][0][c - 1];
  }

    
  static int fine(int x, int y, int l, int r, int u, int d) {
      return Math.max(Math.max(Math.abs(l-x), Math.abs(x-r)), Math.max(Math.abs(y-d), Math.abs(y-u)));
  }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

      StringTokenizer st = new StringTokenizer(br.readLine());
      int r = Integer.parseInt(st.nextToken());
      int c = Integer.parseInt(st.nextToken());

      int[][] blocks = new int[r][c];

      for (int i = 0; i < r; i++) {
        st = new StringTokenizer(br.readLine());

        for (int j = 0; j < c; j++) {
          int item = Integer.parseInt(st.nextToken());
          blocks[i][j] = item;
        }
      }

      int result = oilWell(blocks, r, c);

      bw.write(String.valueOf(result));
      bw.newLine();

      br.close();
      bw.close();
    }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int inf = 1000000000;
const int N = 52;
int dp[N][N][N][N], a[N][N];

int ab(int x) {
    return (x > 0)?x:(-x);
}

int dis(int x1,int y1,int x2,int y2) {
    return max(ab(x1 - x2), ab(y1 - y2));
}

int cal(int x,int y,int x1,int y1,int x2, int y2) {
    return max(dis(x,y,x1,y1), dis(x,y,x2,y2));
}


int main() {  
    int m, n;
    scanf("%d%d",&m,&n);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d",&a[i][j]);
        }
    }
    for (int i = m - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            for (int k = i; k < m; ++k) {
                for (int h = (k == i)?(j + 1):j; h < n; ++h) {
                    dp[i][j][k][h] = inf;

                    if (i < k) {
                        int may = dp[i + 1][j][k][h]; 
                        for (int y = j; y <= h; ++y) {
                            if (a[i][y]) {
                                may += cal(i, y, i + 1, j, k, h);
                            }

                        }
                        dp[i][j][k][h] = min(dp[i][j][k][h], may);
                        may = dp[i][j][k - 1][h];
                        for (int y = j; y <= h; ++y) {
                            if (a[k][y]) {
                                may += cal(k, y, i ,j, k - 1, h);

                            }
                        }
                        dp[i][j][k][h] = min(dp[i][j][k][h], may);
                    }
                    if (j < h) {
                        int may = dp[i][j + 1][k][h];
                        for (int x = i; x <= k; ++x) {
                            if (a[x][j]) {
                                may += cal(x, j, i, j + 1, k, h);
                            }
                        }
                        dp[i][j][k][h] = min(dp[i][j][k][h], may);
                        may = dp[i][j][k][h - 1];
                        for (int x = i; x <= k; ++x) {
                            if (a[x][h]) {
                                may += cal(x, h, i, j, k, h - 1);
                            }
                        }
                        dp[i][j][k][h] = min(dp[i][j][k][h], may);

                    }

                }
            }
        }
    }
    printf("%dn",dp[0][0][m - 1][n - 1]);
    return 0;
}

Problem solution in C.

#include <stdio.h>

int a[55][55][55][55],b[55][55],t,i,j,k,l,m,n,r,c,dy,dx;
int z[55][55][55],v[55][55][55],u;

int main()
{

scanf("%d %d", &r, &c);

for(i=0;i<r;i++)
 for(j=0;j<c;j++)
  scanf("%d",&b[i][j]);

for(i=0;i<c;i++)
 for(j=0;j<r;j++)
 {
   z[j][j][i] = b[j][i];
   for(k=j+1;k<r;k++) z[j][k][i] = z[j][k-1][i] + b[k][i]; 
 }

for(i=0;i<r;i++)
 for(j=0;j<c;j++)
 {
   v[i][j][j] = b[i][j];
   for(k=j+1;k<c;k++) v[i][j][k] = v[i][j][k-1] + b[i][k]; 
 }

u = -1;

for(dy=0;dy<r;dy++) 
 for(dx=0;dx<c;dx++)
  for(i=0;i+dy<r;i++)
   for(j=0;j+dx<c;j++)

    {
      k = i+dy;
      l = j+dx;
    
       m = 2000000000; 
    
      if(k==i && l==j) m = 0;
    
      if(k-i >= l-j && k-i > 0)
       {
         t = a[i+1][j][k][l];  
         if(v[k][j][l]) 
           {
            t +=  v[i][j][l]*(k-i);
            if(t<m) m = t;
           }

         t = a[i][j][k-1][l];  
         if(v[i][j][l]) 
           {
            t +=  v[k][j][l]*(k-i);
            if(t<m) m = t;       
           }
       }    
    
      if(k-i <= l-j && l-j > 0)
       {
         t = a[i][j+1][k][l];  
         if(z[i][k][l]) 
          {
           t +=  z[i][k][j]*(l-j);
           if(t<m) m = t;
          }

         t = a[i][j][k][l-1];  
         if(z[i][k][j]) 
          {
           t +=  z[i][k][l]*(l-j);
           if(t<m) m = t;       
          }
       }    
    
      a[i][j][k][l] = m;    
   
   if(m!=2000000000 && m > u) u = m;
   
    }  

if(u<0) u = 0;

printf("%dn",u);

return 0;
}