Magical Land - Editorial

editorial
,
1

Practice :

Contest Page :

Author:
CodeAsylums

Tester :
CodeAsylums

Editorialist:
jalakp19

DIFFICULTY

CakeWalk

PREREQUISITES:

None

PROBLEM:

Given a 2D Matrix (MxN) of Characters, Find the Maximum Sub-Square which contains only the letter 'T'.

CONSTRAINTS:
1<=M,N<=100

QUICK EXPLANATION:
Simple brute-force to check for each and every square sub matrix would do the trick

EXPLANATION:
Assume each cell to be the top-left cell of the square and check if it contains only the letter ‘T’. If No then stop and move to the next cell else increase the length of the square by 1 and repeat the process. Maintain a variable which would store the maximum size of the square encountered till now. IMPORTANT: Make sure that the sub-square you choose should always be within the limits of MxN.

SOLUTION:

//created by jalakp19
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

char a[105][105];

ll solve(ll i,ll j,ll k)
{
bool flag=true;

for(ll ii=i;ii<i+k;ii++)
{
	for(ll jj=j;jj<j+k;jj++)
	{
		if(a[ii][jj]!='T')
		{
			flag=false;
			break;
		}
	}
	if(flag==false)
		break;
}

if(flag)
	return k*k;
else
	return 0;

}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

ll n{},m{};
cin>>n>>m;

for(ll i=0;i<n;i++)
{
	for(ll j=0;j<m;j++)
	{
		cin>>a[i][j];
	}
}

ll ans{LLONG_MIN};

for(ll i=0;i<n;i++)
{
	for(ll j=0;j<m;j++)
	{
		for(ll k=1;k<=min(n-i,m-j);k++)
		{
			ll temp=solve(i,j,k);
			ans=max(ans,temp);
		}
	}
}

cout<<ans<<endl;
return 0;

}