HDU 1505 City Game -

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1505

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1000+10;
int h[maxn][maxn],l[maxn],r[maxn];
int main()
{int T,R,C; cin>>T;char ch; while(T--&&scanf("%d %d",&R,&C)!=EOF){memset(h,0,sizeof(h));for(int i=0;i<R;i++)for(int j=0;j<C;j++){cin>>ch;h[i][j]= ( ch=='F'&&i-1>=0?h[i-1][j]:0 ) + (ch=='F');    }int maxA=0;for(int i=0;i<R;i++){l[0]=0; r[C-1]=C-1;for(int j=1;j<C;j++){int t=j;while(t>0&&h[i][t-1]>=h[i][j]) t=l[t-1];l[j]=t;}for(int j=C-2;j>=0;j--){int t=j;while(t<C-1&&h[i][t+1]>=h[i][j]) t=r[t+1];r[j]=t;}for(int j=0;j<C;j++)maxA=max(maxA,(r[j]-l[j]+1)*h[i][j]);}cout<<maxA*3<<endl;}return 0;
}