1 //Accepted    5196 KB    109 ms  2 //类似hdu1506  3 //输入数据的格式没有明确的限制  4 //可能出现以下情况  5 //5 5  6 //R  7 //F  8 //F F F  9 //F F F F F 10 //R R R 11 //R R 12 //R F R F R 13 //R R R R R 14 #include <cstdio> 15 #include <cstring> 16 #include <iostream> 17 using namespace std; 18 const int imax_n = 1005; 19 bool map[imax_n][imax_n]; 20 int a[imax_n][imax_n]; 21 int l[imax_n],r[imax_n]; 22 int n,m; 23 void getA() 24 { 25     for (int i=1;i<=n;i++) 26     { 27         for (int j=1;j<=m;j++) 28         { 29             a[i][j]=0; 30             int t=i; 31             while (t>0 && map[t][j]==1) 32             { 33                 a[i][j]++; 34                 t--; 35             } 36         } 37     } 38    // for (int i=1;i<=n;i++) 39     //{ 40     //    for (int j=1;j<=m;j++) 41     //    printf("%d ",a[i][j]); 42     //    printf("\n"); 43     //} 44 } 45 void Dp() 46 { 47     getA(); 48     int ans=0; 49     for (int i=1;i<=n;i++) 50     { 51         l[1]=1; 52         a[i][0]=-1; 53         for (int j=2;j<=m;j++) 54         { 55             int t=j; 56             while (a[i][j]<=a[i][t-1]) 57             { 58                 t=l[t-1]; 59             } 60             l[j]=t; 61         } 62         r[m]=m; 63         a[i][m+1]=-1; 64         for (int j=m-1;j>=1;j--) 65         { 66             int t=j; 67             while (a[i][j]<=a[i][t+1]) 68             { 69                 t=r[t+1]; 70             } 71             r[j]=t; 72         } 73         for (int j=1;j<=m;j++) 74         if (a[i][j]*(r[j]-l[j]+1)>ans) 75         ans=a[i][j]*(r[j]-l[j]+1); 76     } 77     printf("%d\n",3*ans); 78 } 79 char s[5]; 80 int main() 81 { 82     int T; 83     while (scanf("%d",&T)!=EOF) 84     { 85         while (T--) 86         { 87             scanf("%d%d",&n,&m); 88             for (int i=1;i<=n;i++) 89             { 90                 for (int j=1;j<=m;j++) 91                 { 92                     scanf("%s",s); 93                     if (s[0]==‘F‘) 94                     map[i][j]=1; 95                     else 96                     map[i][j]=0; 97                 } 98             } 99         //for (int i=1;i<=n;i++)100         //{101          //   for (int j=1;j<=m;j++)102          //   printf("%d",map[i][j]);103          //   printf("\n");104         //}105             Dp();106         }107     }108     return 0;109 }