HackerRank Mr. K marsh problem solution

In this Hackerrank Mr. K marsh problem solution, we have given a rectangular plot of land which may have marshes where fenceposts cannot be set and we need to find the perimeter of the largest rectangular fence that can be built on this land.

Problem solution in Python.

#!/bin/python3

import os
import sys


#
# Complete the kMarsh function below.
#
def kMarsh(grid):
    #
    # Write your code here.
    #
    rows = len(grid)
    cols = len(grid[0])
    up = [[0] * cols for _ in range(rows)]
    left = [[0] * cols for _ in range(rows)]
    for i in range(rows):
        for j in range(cols):
            if j > 0:
                left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
            if i > 0:
                up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
    max_perimeter = 0
    for i in range(1, rows):
        for j in range(1, cols):
            if grid[i][j] != 'x':
                a = i - up[i][j]
                b = 0
                while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
                    b = max(j - left[a][j], j - left[i][j])
                    while up[i][b] < i - a and b < j and 2 * (i - a) + 2 * (j - b) > max_perimeter:
                        b += 1
                    if b < j and left[i][j] >= j - b and grid[a][b] != 'x':
                        max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
                    a += 1
                    b = 0
    print(max_perimeter if max_perimeter > 0 else 'impossible')


if __name__ == '__main__':
    mn = input().split()

    m = int(mn[0])

    n = int(mn[1])

    grid = []

    for _ in range(m):
        grid_item = input()
        grid.append(grid_item)

    kMarsh(grid)

Problem solution in Java.

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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc= new Scanner(System.in);
        int m= sc.nextInt();
        int n= sc.nextInt();
        int[][] arr = new int[m][n];
        int[][] dp= new int[m][m];
        for(int i=0;i<m;i++){
             char[] ch= sc.next().toCharArray();
            for(int j=0;j<n;j++){
                if(ch[j]=='.')
                    arr[i][j]=1;
                else
                    arr[i][j]=0;
            }
        }
        int ans=0;
      for(int i=0;i<m;i++){
          for(int j=0;j<m;j++){
              dp[i][j]=-1;
          }
      }
      for(int i=0;i<n;i++){
          for(int j=0;j<m;j++){
              boolean flag=true;
              for(int k=j+1;k<m;k++){
                  if(arr[k][i]==0)
                      flag=false;
                  if(arr[k][i]==1 && arr[j][i]==1){ 
                      if(dp[j][k]>=0)
                      dp[j][k]+= 1;
                      else if(flag){
                          dp[j][k]=0;
                      }
                      if(flag && dp[j][k]>0){
                      int a= 2*(dp[j][k]+k-j);
                      if(ans<a){
                          //System.out.println(k+" "+j+" "+dp[j][k]);
                          ans=a;
                      }
                      }
                  }
                  else
                      dp[j][k]=-1;
              }
          }
      } 
        if(ans>0)
          System.out.println(ans);
        else
          System.out.println("impossible");
    }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

const int N = 505;
int M[N][N], U[N][N], L[N][N];

int main() {
    char ch;
    int rows, cols;
    cin >> rows >> cols;
    FOR( r, 1, rows )
        FOR( c, 1, cols ) {
            cin >> ch;
            M[r][c] = ch == '.';
        }
    FOR( r, 1, rows )
        FOR( c, 1, cols ) {
            U[r][c] = M[r][c] ? U[r-1][c] + 1 : 0;
            L[r][c] = M[r][c] ? L[r][c-1] + 1 : 0;
        }
    int maxL = 0, maxU = 0;
    FOR( r, 1, rows )
        FOR( c, 1, cols )
            FORD( k, U[r][c]-1, 1 ) {
                /*
                    xxxC1
                    xxxC2
                    xxxB
                */
                FORD( l, min( L[r][c], L[r-k][c] )-1, 1 ) {
                    if ( U[r][c-l] > k ) {
                        if ( l + k > maxL + maxU )
                            maxL = l, maxU = k;
                        break;
                    }
                }
            }
    if ( maxL + maxU == 0 )
        cout << "impossible" << endl;
    else
        cout << (maxL + maxU) * 2 << endl;
    return 0;
}

Problem solution in C.

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

/*  not a DP solution  */
int perimeter(int field[500][500],int l,int m,int p,int q){
    int isvalid = 1;
    for(int i=p;i<=q && isvalid;i++) {
//        isvalid = isvalid && field[l][i];
        isvalid = isvalid && field[m][i];//only need to test bottom
    }
    for(int i=l+1;i<m && isvalid;i++) {
//        isvalid = isvalid && field[i][p];
        isvalid = isvalid && field[i][q];//only need to test right
    }
    if(isvalid) return m-l+q-p;
    return 0;
}


int find_max(int field[500][500], int M, int N) {
    int maxp = 0;
    int qmax = -1;
    for(int i=0;i<M-1;i++) {
        for(int j=0;j<N-1;j++) {
            if(field[i][j] && field[i][j+1] && field[i+1][j]) {//search for top left corner
                int pmax=i+1;
                while(field[pmax+1][j] && pmax<M-1) pmax++;
                if(j>qmax) {
                    qmax = j+1;
                    while(field[i][qmax+1] && qmax<N-1) qmax++;
                }
                for(int p=pmax;p>i;p--){
                    int minq = maxp-p+i+j-1;
                    if(minq<j) minq = j;
                    for(int q=qmax;q>minq;q--) {//consider rectangle from (i,j) to (p,q)
                        if(field[p-1][q] && field[p][q-1] && field[p][q]) {//bottom right corner
                            int test = perimeter(field,i,p,j,q);
                            if(test>maxp) maxp=test;
                        }
                    }
                }
            }
        }
        qmax = -1;
    }
    return maxp;
}


int main() {
    int field[500][500],M,N;
    char c;
    scanf("%d %d",&M,&N);
    scanf("%c",&c);//flush EOL
    for(int im=0;im<M;im++) {
        for(int in=0;in<N;in++) {
            scanf("%c",&c);
            field[im][in] = 1;
            if(c==120)field[im][in] = 0;
        }
        scanf("%c",&c);//flush EOL
    }
    int perimeter = find_max(field,M,N);
    if(perimeter) {
        printf("%dn",2*perimeter);
    } else {
        printf("impossiblen");
    }
    return 0;
}