HDU - 1505 City Game（单调栈）_综合

HDU - 1505 City Game（单调栈）

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
char g[N][N]; 
int h[N][N];//存图 
int q[N],l[N],r[N];//单调栈,左边界和右边界 
int work(int h[])
{
    h[0]=h[m+1]=-1;//左边界 int tt=0;//tt表示栈顶q[0]=0;for(int i=1;i<=m;i++){
    while(h[q[tt]]>=h[i]) tt--;//往左找到第一个比h[i]小的位置为止l[i]=q[tt];//记录第一个比h[i]小的矩形的位置q[++tt]=i;//添加当前矩形到栈中}//右边界tt=0;q[0]=m+1;for(int i=m;i>=1;i--){
    while(h[q[tt]]>=h[i]) tt--;r[i]=q[tt];q[++tt]=i;} //更新矩形最大值 int res=0;for(int i=1;i<=m;i++)res=max(res,h[i]*(r[i]-l[i]-1));return res;
}
int main()
{
    int t;cin>>t;while(t--){
    cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
    cin>>g[i][j];if(g[i][j]=='F') h[i][j]=h[i-1][j]+1;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;
}