Question Name:Rectangular Land

#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;


/* Prewritten code begins */
#define REP(i,n)    for(int i=0; i<(n); ++i)
#define FOR(i,a,b)  for(int i=(a); i<=(b); ++i)
/* Prewritten code ends */

const int maxN = 505;
string s[maxN];
int range[maxN][maxN];
int main() {
	int R, C, lastC, res = 0;
	cin >> R >> C;
	REP(r,R) cin >> s[r];
	REP(c,C) range[0][c] = s[0][c] == '.' ? 0 : maxN;
	FOR(r,1,R-1) REP(c,C) if(s[r][c] == '.') range[r][c] = min(range[r-1][c], r); else range[r][c] = maxN;
	REP(r1,R) FOR(r2,r1+1,R-1) {
		lastC = -1;
		REP(c,C) {
			if(s[r1][c] == '.' && s[r2][c] == '.') {
				if(range[r2][c] <= r1) {
					if(lastC != -1) res = max(res, 2*(r2-r1-1)+2*(c-lastC+1));
					else lastC = c; 
				}
			} else {
				lastC = -1;
			}
		}
	}
	if(res == 0) cout << "impossible" << endl;
	else cout << res << endl;
	return 0;
}
  • Problem Description

    Mr K has a rectangular land of size m X n. There are marshes in the land where the fence cannot hold. Mr K wants you to find the perimeter of the largest rectangular fence that can be built on this land. 

    Input format

    The first line contains m and n. The next m lines contain n characters each describing the state of the land. ‘x’ (ascii value: 120) if it is a marsh and ‘.’ ( ascii value:46) otherwise.

    Constraints
    2<=m,n<=500 

    Output Format

    Output contains a single integer – the largest perimeter. If the rectangular fence cannot be built, print “”impossible”” (without quotes).


  • Test Case 1
    Input (stdin)4 5
    …..
    .x.x.
    …..
    …..
    Expected Output14
  • Test Case 2
    Input (stdin)2 2
    .x
    x.
    Expected Outputimpossible

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro