http://acm.hdu.edu.cn/showproblem.php?pid=1505
先处理每一行上每一个F为底往上所到达的高度，然后再左右处理。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 1001 5 using namespace std; 6 7 int t; 8 int n,m; 9 int a[maxn][maxn]; 10 int l[maxn],r[maxn]; 11 12 int main() 13 { 14 scanf("%d",&t); 15 while(t--) 16 { 17 scanf("%d%d",&n,&m); 18 getchar(); 19 memset(a,0,sizeof(a)); 20 for(int i=1; i<=n; i++) 21 { 22 for(int j=1; j<=m; j++) 23 { 24 char s[10]; 25 scanf("%s",s); 26 if(s[0]=='F') a[i][j]=a[i-1][j]+1; 27 else a[i][j]=0; 28 } 29 } 30 int max1=-1; 31 for(int i=1; i<=n; i++) 32 { 33 a[i][0]=a[i][m+1]=-1; 34 for(int j=1; j<=m; j++) 35 l[j]=r[j]=j; 36 for(int j=1; j<=m; j++) 37 { 38 while(a[i][j]<=a[i][l[j]-1]) l[j]=l[l[j]-1]; 39 } 40 for(int j=m; j>=1; j--) 41 { 42 while(a[i][j]<=a[i][r[j]+1]) r[j]=r[r[j]+1]; 43 } 44 for(int j=1; j<=m; j++) 45 { 46 int ans=a[i][j]*(r[j]-l[j]+1); 47 if(ans>max1) 48 max1=ans; 49 } 50 } 51 printf("%d ",max1*3); 52 } 53 return 0; 54 }