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