Solution :

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

In-depth Explanation of the Code

This problem involves finding the largest rectangular fence (perimeter) that can be built on a rectangular grid of size $m \times n$ , where some cells are marshes ('x') and some are land ('.'). The fence can only be built on land, meaning we can only form a rectangle using '.' cells.

Let's break down the code and the problem-solving approach:

Problem Understanding

The input consists of:

$R$ (number of rows) and $C$ (number of columns).
A grid of size $R \times C$ $R \times C$ where each cell is either:
- . representing land, where a fence can be built.
- x representing a marsh, where a fence cannot be built.

The task is to compute the largest perimeter of any rectangle formed entirely on land (.). If no such rectangle exists, we need to return "impossible".

Key Concepts

Valid Rectangle: A valid rectangle is one where the top and bottom edges, as well as the vertical sides, are formed entirely by . cells.
Largest Perimeter: The perimeter of a rectangle is given by $2 \times (length + width)$ . The goal is to maximize this value for any valid rectangle.

Approach and Code Walkthrough

The code employs a dynamic programming strategy to solve the problem efficiently, given the constraints.

Step-by-Step Code Explanation:

Input Parsing:
```
int R, C, lastC, res = 0;
cin >> R >> C;
REP(r, R) cin >> s[r];
```
- First, the number of rows $R$ and columns $C$ are read from input.
- Then, the grid is input row by row into a string array s[], where each element of s corresponds to a row in the grid.
Initialize a range Array:
```
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;
```
- range[r][c] keeps track of how far up we can go from the cell (r, c) and still have land (.).
- If the current cell is . (land), we check the cell directly above it. If the cell above is also . (land), we propagate the minimum of the current row index or the value from above. This gives us the largest possible height for any rectangle ending at (r, c) and extending upwards.
- If the current cell is x (marsh), we assign a very large value maxN (representing an invalid area for forming a rectangle).
Finding the Largest Perimeter:
```
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;
    }
  }
}
```
- Outer Loop (Rectangle Rows):
  - We select two distinct rows r1 and r2 (with r2 > r1) to define the top and bottom of the rectangle.
- Inner Loop (Columns):
  - For each column, we check if both s[r1][c] and s[r2][c] are .. This means that the top and bottom edges of the rectangle can be formed along these rows at column c.
  - The range[r2][c] <= r1 condition ensures that all cells between rows r1 and r2 are valid land cells (.), and hence a valid rectangle can be formed.
- Tracking Largest Perimeter:
  - If a valid rectangle is found, we calculate the perimeter using the formula:
    $\text{Perimeter} = 2 \times (\text{Height} + \text{Width})$
    where:
    - Height = $r2 - r1 - 1$ (the number of rows between r1 and r2, excluding the borders).
    - Width = $c - \text{lastC} + 1$ (the number of columns between the leftmost and current column forming the rectangle).
  - Updating Last Column (lastC):
    - The variable lastC stores the leftmost column where a valid rectangle edge is found. If no valid column exists, it is reset to -1.
Output:
```
if(res == 0) cout << "impossible" << endl;
else cout << res << endl;
```
- After processing all possible pairs of rows and columns, if no valid rectangle was found (res == 0), we print "impossible".
- Otherwise, we output the largest perimeter found.

Detailed Example Walkthrough

Test Case 1:


Input:
4 5
.....
.x.x.
.....
.....

Rows (r1 = 0, r2 = 2):
- For these rows, valid land cells can form a rectangle between column 0 and 4. The largest rectangle spans the entire width between columns 0 and 4, and the height is 1 (since r2 - r1 - 1 = 1).
- The perimeter is $2 \times (1 + 5) = 14$ .
The answer is 14.

Test Case 2:


Input:
2 2
.x
x.

There are no two rows where valid land cells can form a rectangle, so the output is "impossible".

Complexity Analysis

Time Complexity:
- The outer loop iterates over all pairs of rows, which takes $O(R^2)$ .
- The inner loop iterates over all columns for each pair of rows, which takes $O(C)$ .
- Thus, the overall time complexity is $O(R^2 \times C)$ .
Given that $R, C \leq 500$ , the time complexity $O(500^2 \times 500) = O(125,000,000)$ is efficient enough for this problem's constraints.
Space Complexity:
- We use an auxiliary range array of size $R \times C$ , which takes $O(R \times C)$ space.
- Thus, the space complexity is $O(R \times C)$ .

Scholar Career Network

Question Name:Rectangular Land - SRM DSA ELAB