AcWing 152. 城市游戏
原题链接
中等
作者:
阴天快乐
,
2021-05-20 22:55:30
,
所有人可见
,
阅读 352
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;//n行m列
int h[N][N];//每一行每一个点上面有多少个F(包括当前这个点);
char g[N][N]; //存放当前这个图;
stack<int>sta;//单调栈
//得到每一行的最大子矩形面积。
int work(int a[]){
int res=0;
a[0]=-1;
a[m+1]=-1;
for(int i=0;i<=m+1;i++){
while(!sta.empty()&&a[sta.top()]>a[i]){
int temp=sta.top();
sta.pop();
int left=sta.top();
int right=i;
res=max(res,(right-left-1)*a[temp]);
//cout<<res<<endl;
}
sta.push(i);
}
return res;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c;
cin>>c;
g[i][j]=c;
if(c=='F') h[i][j]=h[i-1][j]+1; //第i行和第i-1行的F之间的递推关系;
else h[i][j]=0;
}
}
int res=0;
for(int i=1;i<=n;i++){
res=max(res,work(h[i]));
}
cout<<res*3<<endl;
return 0;
}