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.