题意
其实就是BZOJ3039 不过没权限号(粗鄙之语)
同时也是洛谷4147
就是求最大子矩阵然后*3
思路
悬线法
有个博客讲的不错https://blog.csdn.net/u012288458/article/details/48197727
GREED-VI大佬之前也讲过,友链一下https://www.cnblogs.com/GREED-VI/p/9887399.html (他说的其实是悬线法,扫描线和这个不一样的吧)
代码
水水水
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 1005
using namespace std;
int n,m;
int ans;
int up[N][N],L[N][N],R[N][N];
pair<int,int> st[N];
bool v[N][N],f_fall;
void init()
{
char ch;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
cin>>ch;
v[i][j]=(ch=='F'?:);
if(v[i][j]) f_fall=;
}
}
void solve()
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(!v[i][j])
up[i][j]=;
else up[i][j]=up[i-][j]+;
for (int i=;i<=n;i++)
{
int top=;
st[++top]=make_pair(-,);
for (int j=;j<=m;j++)
{
while (up[i][j]<=st[top].first) top--;
L[i][j]=j-st[top].second-;
st[++top]=make_pair(up[i][j],j);
}
}
for (int i=;i<=n;i++)
{
int top=;
st[++top]=make_pair(-,m+);
for (int j=m;j>=;j--)
{
while (up[i][j]<=st[top].first) top--;
R[i][j]=st[top].second-j-;
st[++top]=make_pair(up[i][j],j);
}
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
ans=max(ans,(L[i][j]+R[i][j]+)*up[i][j]);
ans*=;
}
int main()
{
//freopen("cpp.in","r",stdin);
//freopen("cpp.out","w",stdout);
int Q;scanf("%d",&Q);
while(Q--)
{
f_fall=;
init();
if(f_fall==) printf("0\n");
else{
solve();
printf("%d\n",ans);
ans=;
memset(v,,sizeof(v));
memset(up,,sizeof(up));
memset(L,,sizeof(L));
memset(R,,sizeof(R));
memset(st,,sizeof(st));
}
}
return ;
}