HackerRank Mr K marsh Problem Solution
In this post, we will solve HackerRank Mr K marsh Problem Solution.
Mr K has a rectangular plot of land which may have marshes where fenceposts cannot be set. He wants you to find the perimeter of the largest rectangular fence that can be built on this land.
For example, in the following m x n = 4 x 4 grid, æ marks a marsh and . marks good
land.
....
..x.
..x.
x...If we number the rows and columns starting with 1. we see that there are two main areas that can be fenced: (1, 1) (3,2) and (1, 2) (4, 4). The longest perimeter is 10.
Function Description
Complete the kMarsh function in the editor below. It should print either an integer or impossible.
kMarsh has the following parameter(s):
- grid: an array of strings that represent the grid
Input Format
The first line contains two space-separated integers m and n. the grid rows and columns. Each of the next m lines contains n characters each describing the state of the land. ‘x’ (ascii value: 120) if it is a marsh and !! ( ascii value:46) otherwise.
Output Format
Output contains a single integer – the largest perimeter. If the rectangular fence cannot be
built, print impossible.
Sample Input 0
4 5
.....
.x.x.
.....
.....
Sample Output 0
14ample Input 1
2 2
.x
x.
Sample Output 1
impossible
Explanation 1
We need a minimum of 4 points to place the 4 corners of the fence. Hence, impossible.
Sample Input 2
2 5
.....
xxxx.
Sample Output 2
impossible 
Mr K marsh C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
typedef struct{
int x, y;
}coord;
int min(int a, int b){
if(a < b)
return a;
return b;
}
int max(int a, int b){
if(a > b)
return a;
return b;
}
int main() {
//freopen("input.txt", "r", stdin);
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
//Input
int m, n, i, j;
scanf("%d", &m);
scanf("%d", &n);
char A[m][n+1];
coord C[m+1][n+1];
for(i = 0; i < m; i++){
scanf("%s", &A[i]);
}
//Start logic
//Initialization
memset(C, 0, sizeof(C));
for(i = 0; i < m; i++){
for(j = 0; j < n; j++){
if(A[i][j] == '.'){
C[i+1][j+1].x = C[i-1+1][j+1].x + 1;
C[i+1][j+1].y = C[i+1][j-1+1].y + 1;
}
if(A[i][j] == 'x'){
C[i+1][j+1].x = 0;
C[i+1][j+1].y = 0;
}
}
}
int x, y, k, p = 0;
//printf("%d %d\n", m, n);
for(i = m; i > 1; i--){
for(j = n; j > 1; j--){
if(C[i][j].x != 0 && C[i][j].x != 1 && C[i][j].y != 1){
//Fixing column
k = C[i][j].x;
y = min(C[i-k+1][j].y, C[i][j].y);
while(C[i][j-y+1].x < k)
y--;
while(k > 1){
if(y > 1){
int p1 = 2 * (k - 1) + 2 * (y - 1);
p = max(p1, p);
}
k--;
y = min(C[i-k+1][j].y, C[i][j].y);
while(C[i][j-y+1].x < k)
y--;
}
//Fixing row
/* k = C[i][j].y;
x = min(C[i][j-k+1].x, C[i][j].x);
while(C[i-x+1][j].y < k)
x--;
while(k > 1 && x > 1){
int p1 = 2 * (k - 1) + 2 * (x - 1);
p = max(p1, p);
k--;
x = min(C[i][j-k+1].x, C[i][j].x);
while(C[i-x+1][j].y < k)
x--;
}*/
}
}
}
if(p <= 0)
printf("impossible\n");
else
printf("%d\n", p);
/*for(i = 0; i < m; i++){
for(j = 0; j < n; j++)
printf("%c ", A[i][j]);
printf("\n");
}
printf("\n");
for(i = 1; i <= m; i++){
for(j = 1; j <= n; j++)
printf("(%d, %d) ", C[i][j].x, C[i][j].y);
printf("\n");
}*/
return 0;
}Mr K marsh C++ Solution
#include <iostream>
#include <vector>
using namespace std;
const int NO_ERR = 0;
const int UPROW_ERR = 1;
const int DOWNROW_ERR = 2;
const int LEFTCOL_ERR = 4;
const int RIGHTCOL_ERR = 8;
vector<char> rowVec;
vector<vector<char>> mainVec;
#define CHECKPOINT(i,j) \
(mainVec.at((i)).at((j)) == 'x')
int checkRect(int i1, int j1, int i2, int j2)
{
int tcheckRet = NO_ERR;
int out1 = 0;
int out2 = 0;
// ROW check.
for (int k=j1; k<=j2; k++)
{
if ((out1 == 1) && (out2 == 1))
break;
if ((out1 == 0) && CHECKPOINT(i1,k))
{
tcheckRet |= UPROW_ERR;
out1 = 1;
}
if ((out2 == 0) && CHECKPOINT(i2,k))
{
tcheckRet |= DOWNROW_ERR;
out2 = 1;
}
}
out1 = 0;
out2 = 0;
// COL check.
for (int k=i1; k<=i2; k++)
{
if ((out1 == 1) && (out2 == 1))
break;
if ((out1 == 0) && CHECKPOINT(k,j1))
{
tcheckRet |= LEFTCOL_ERR;
out1 = 1;
}
if ((out2 == 0) && CHECKPOINT(k,j2))
{
tcheckRet |= RIGHTCOL_ERR;
out2 = 1;
}
}
return tcheckRet;
}
int main()
{
int M,N;
cin >> M >> N;
// Get the Matrix input.
rowVec.assign(N,0);
for (int i=0; i<M; i++)
{
for (int j=0; j<N; j++)
{
cin >> rowVec.at(j);
}
mainVec.push_back(rowVec);
}
// check loop begins.
int tcheckRet = NO_ERR;
int length = 0;
int lengthMax = 0;
for (int i1=0; i1<M-1; i1++)
{
for (int j1=0; j1<N-1; j1++)
{
if (CHECKPOINT(i1,j1))
continue;
if (CHECKPOINT(i1,j1+1))
continue;
if (CHECKPOINT(i1+1,j1))
continue;
// look for the first left col marsh.
// |
// V
int weak1 = 0;
for (weak1=i1+2; weak1<M; weak1++)
{
if CHECKPOINT(weak1,j1)
break;
}
// look for the first top row marsh. ->
int weak2 = 0;
for (weak2=j1+2; weak2<N; weak2++)
{
if CHECKPOINT(i1,weak2)
break;
}
if (((weak2-1-j1) + (weak1-1-i1)) < lengthMax/2)
{
//break;
continue;
}
//for (int i2=M-1; i2>=i1+1; i2--)
for (int i2=weak1-1; i2>=i1+1; i2--)
{
// look for the first bottom row marsh. ->
int weak3 = 0;
for (weak3=j1+1; weak3<=weak2-1; weak3++)
{
if CHECKPOINT(i2,weak3)
break;
}
//for (int j2=N-1; j2>=j1+1; j2--)
for (int j2=weak3-1; j2>=j1+1; j2--)
{
tcheckRet = checkRect(i1,j1,i2,j2);
if (tcheckRet == NO_ERR)
{
length = 2*(i2-i1+j2-j1);
if (length > lengthMax)
lengthMax = length;
break;// to the next row.
}
else
continue;
}
}
}
}
if (lengthMax == 0)
cout << "impossible" << endl;
else
cout << lengthMax << endl;
return 0;
}Mr K marsh C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
/*
* Complete the kMarsh function below.
*/
static void kMarsh(string[] grid)
{
int N = grid[0].Length;
int M = grid.Length;
int[,] longestFence = new int[N, N];
int maxPerimeter = 0;
for (int i = 0; i < M; i++)
{
string line = grid[i];
int[] xCount = new int[N + 1];
for (int j = 0; j < N; j++)
{
xCount[j + 1] = xCount[j] + (line[j] != '.' ? 1 : 0);
}
for (int j = 0; j < N - 1; j++)
{
for(int k = j + 1; k < N; k++)
{
if(line[j]=='.' && line[k] == '.')
{
bool allDots = xCount[k] - xCount[j] == 0;
if (longestFence[j, k] == 0)
{
if (allDots) longestFence[j, k] = 1;
}
else
{
longestFence[j, k]++;
if (allDots)
{
int perimeter = (k - j - 1) * 2 + longestFence[j, k] * 2;
maxPerimeter = Math.Max(maxPerimeter, perimeter);
}
}
}
else
{
longestFence[j, k] = 0;
}
}
}
}
Console.WriteLine(maxPerimeter > 0 ? "" + maxPerimeter : "impossible");
}
static void Main(string[] args)
{
string[] mn = Console.ReadLine().Split(' ');
int m = Convert.ToInt32(mn[0]);
int n = Convert.ToInt32(mn[1]);
string[] grid = new string[m];
for (int gridItr = 0; gridItr < m; gridItr++)
{
string gridItem = Console.ReadLine().TrimEnd();
grid[gridItr] = gridItem;
}
kMarsh(grid);
}
}Mr K marsh Java Solution
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");
}
}Mr K marsh JavaScript Solution
'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
class Component {
constructor(parent, size) {
this.parent = parent;
this.size = size;
}
}
class UnionFind {
constructor(n) {
this.components = new Array(n);
this.componentsCount = n;
for (let i = 0; i < n; i++) {
// Link to itself (self root)
// Each component is originally of size one
this.components[i] = new Component(i, 1);
}
}
// A utility function to find set of an element i (uses path compression technique)
find(i) {
if (this.components[i].parent !== i) {
this.components[i].parent = this.find(this.components[i].parent);
}
return this.components[i].parent;
}
// A utility function that does union of two sets of x and y (uses union by rank)
union(x, y) {
let xroot = this.find(x);
let yroot = this.find(y);
if (xroot == yroot) {
// These elements are already in the same group!
return;
}
// Merge smaller component/set into the larger one.
if (this.components[xroot].size < this.components[yroot].size) {
this.components[yroot].size += this.components[xroot].size;
this.components[xroot].parent = yroot;
} else {
this.components[xroot].size += this.components[yroot].size;
this.components[yroot].parent = xroot;
}
// Since the roots found are different we know that the number of components/sets has decreased by one
this.componentsCount--;
}
// Return whether or not the elements 'p' and 'q' are in the same components/set.
isConnected(p, q) {
return this.find(p) == this.find(q);
}
// Return the size of the components/set 'p' belongs to
getComponentSize(p) {
return this.components[this.find(p)].size;
}
// Return the number of elements in this UnionFind/Disjoint set
size() {
return this.components.length;
}
// Returns the number of components/sets
getComponentsCount() {
return this.componentsCount;
}
getRootComponents() {
const rootComponents = new Array(this.componentsCount);
let rootComponentsIndex = 0;
for (let index = 0; index < this.size(); index++) {
const component = this.components[index];
if (component.parent === index) {
rootComponents[rootComponentsIndex] = {
index: index,
size: component.size
};
rootComponentsIndex++;
}
}
return rootComponents;
}
}
function kMarsh(grid) {
const nCols = grid[0].length;
const nRows = grid.length;
const size = nRows * nCols;
const horizontalSets = new UnionFind(size);
for (let row = 0; row < nRows; row++) {
const s = grid[row];
for (let col = 1; col < nCols; col++) {
if (s[col - 1] === "." && s[col] === ".") {
horizontalSets.union(id(row, col - 1), id(row, col));
}
}
}
const verticalSets = new UnionFind(size);
for (let col = 0; col < nCols; col++) {
for (let row = 1; row < nRows; row++) {
if (grid[row - 1][col] === "." && grid[row][col] === ".") {
verticalSets.union(id(row - 1, col), id(row, col));
}
}
}
let maxPerimeter = 0;
for (let row = 0; row < nRows - 1; row++) {
const s = grid[row];
// for (let col = 0; col < nCols - 1; col++) {
// if (s[col] === ".") {
// const componentId = id(row, col);
// const componentSize = horizontalSets.getComponentSize(componentId);
// for (let i = col; i < col + componentSize - 1; i++) {
// processHorizontalSet(row, i, col + componentSize - 1);
// }
// }
// }
let col = 0;
while (col < nCols - 1) {
if (s[col] === ".") {
const componentId = id(row, col);
const componentSize = horizontalSets.getComponentSize(componentId);
if (componentSize > 1) {
for (let i = col; i < col + componentSize - 1; i++) {
processHorizontalSet(row, i, col + componentSize - 1);
}
//processHorizontalSet(row, col, col + componentSize - 1);
}
col += componentSize;
} else {
col++;
}
}
}
if (maxPerimeter) {
console.log(maxPerimeter);
} else {
console.log("impossible");
}
function processHorizontalSet(row, startCol, endCol) {
for (let col = endCol; col > startCol; col--) {
const width = col - startCol;
const d = 2 * (nRows - row - 1) + 2 * width;
if (d <= maxPerimeter) {
break;
}
const minHeight = Math.max((maxPerimeter - 2 * width) / 2, 1);
if (!isConnectedVertically(row, Math.min(row + minHeight, nRows - 1), startCol)) {
break;
}
for (let endRow = row + minHeight; endRow < nRows; endRow++) {
const d = 2 * (endRow - row) + 2 * width;
if (isConnectedVertically(row, endRow, startCol) && isConnectedVertically(row, endRow, col)) {
if (isConnectedHorizontally(endRow, startCol, col)) {
maxPerimeter = Math.max(d, maxPerimeter);
}
} else {
break;
}
}
}
}
function id(row, col) {
return row * nCols + col;
}
function isConnectedHorizontally(row, col1, col2) {
const point1 = id(row, col1);
const point2 = id(row, col2);
return horizontalSets.isConnected(point1, point2);
}
function isConnectedVertically(row1, row2, col) {
const point1 = id(row1, col);
const point2 = id(row2, col);
return verticalSets.isConnected(point1, point2);
}
}
function main() {
const mn = readLine().split(' ');
const m = parseInt(mn[0], 10);
const n = parseInt(mn[1], 10);
let grid = [];
for (let gridItr = 0; gridItr < m; gridItr++) {
const gridItem = readLine();
grid.push(gridItem);
}
kMarsh(grid);
}Mr K marsh Python Solution
import sys
m, n = [int(x) for x in next(sys.stdin).strip().split(" ")]
grid = [line.strip() for line in sys.stdin]
max_dists_vert = {k:{} for k in range(m)}
max_dists_horiz = {k:{} for k in range(m)}
for i in range(m):
max_dists_horiz[i][0] = 1*(grid[i][0]=='.')
for j in range(n):
max_dists_vert[0][j] = 1*(grid[0][j]=='.')
for i in range(m):
for j in range(n):
not_marsh = grid[i][j]=='.'
if i > 0:
max_dists_vert[i][j] = max_dists_vert[i-1][j] + 1 if not_marsh else 0
if j > 0:
max_dists_horiz[i][j] = max_dists_horiz[i][j-1] + 1 if not_marsh else 0
#print("horiz:")
#for i in range(m):
# print(" ".join([str(x) for x in max_dists_horiz[i].values()]))
#print("vert:")
#for i in range(m):
# print(" ".join([str(x) for x in max_dists_vert[i].values()]))
best_pair, best_pair_score = None, 0
for i in range(m-1,0,-1):
for j in range(n-1,0,-1):
max_i = max_dists_vert[i][j]
max_j = max_dists_horiz[i][j]
if 2*(max_i+max_j-2) <= best_pair_score: continue
for delta_i in range(max_i,1,-1):
for delta_j in range(max_j,1,-1):
if 2*(delta_i+delta_j-2) <= best_pair_score: continue
i2, j2 = i-delta_i+1, j-delta_j+1
p2_vert, p2_horiz = max_dists_vert[i][j2], max_dists_horiz[i2][j]
if max_dists_vert[i][j2] >= delta_i and max_dists_horiz[i2][j] >= delta_j:
pair = [(i,j), (i2, j2)]
pair_score = 2*(delta_i + delta_j - 2)
#if i == 3 and j == 5:
# print("i:{},j:{},delta_i:{},delta_j:{},i2:{},j2:{},pair_score:{},pair:{}".format(i,j,delta_i,delta_j,i2,j2,pair_score,pair))
if pair_score > best_pair_score:
best_pair, best_pair_score = pair, pair_score
if best_pair_score == 0:
print("impossible")
else:
#print(best_pair)
print(best_pair_score)
