## 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

#### Ads Blocker Detected!!!

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