本题和直方图中的最大矩形很像,建议先做该题。对于读入的NxM的矩形我们可以转换成求n次直方图中的最大矩形,其矩形图长度为M,每次增加一层即n+1的时候矩形图的高度都会变化,然后对于每个矩形的高度我们需要处理一下,如果第n层某一个矩形的上一层即n-1层为’F’的话就把该矩形的高度累加,否则高度就清零,然后按照求直方图的最大矩形来做即可,方法为单调栈
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e3+10,INF=1e8;
char a[N][N];
int s[N],h[N][N],lt[N],rt[N],n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='F')h[i][j]=h[i-1][j]+1;
else h[i][j]=0;
}
int ans=0;
for(int i=1;i<=n;i++)
{
int tt=0;
h[i][0]=h[i][m+1]=-1;
s[tt]=0;
for(int j=1;j<=m;j++)
{
while(h[i][s[tt]]>=h[i][j]) tt--;
lt[j]=s[tt];
s[++tt]=j;
}
tt=0;
s[tt]=m+1;
for(int j=m;j>=1;j--)
{
while(h[i][s[tt]]>=h[i][j]) tt--;
rt[j]=s[tt];
s[++tt]=j;
}
int res=0;
for(int j=1;j<=m;j++)
{
res=max(res,h[i][j]*(rt[j]-lt[j]-1));
}
ans=max(ans,res);
}
cout<<ans*3;
return 0;
}