这题是上一题的升级版
关键在于条形图的构造，逐行处理输入的矩阵，遇到'F'则在上一次的条形图基础上再加1，遇到'R'则置为0
然后用上一题的算法，求每行对应条形图的最大矩阵的面积。
另外：本来是debug都不用就1A的节奏。可在输入数据上，一开始我用的是scanf读入字符 和 getchar跳过无效字符，在测试数据上是没有问题的，但一交上去就WA掉了。
看到别人的代码使用cin读入的。其实，如果输入数据不太大的话，cin还是比较放心好用的。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 1010; 9 char map[maxn][maxn]; 10 int h[maxn], l[maxn], r[maxn]; 11 12 int main(void) 13 { 14 #ifdef LOCAL 15 freopen("1505in.txt", "r", stdin); 16 #endif 17 18 int T; 19 scanf("%d", &T); 20 while(T--) 21 { 22 int row, col; 23 scanf("%d%d", &row, &col); 24 getchar(); 25 int i, j; 26 for(i = 1; i <= row; ++i) 27 for(j = 1; j <= col; ++j) 28 cin >> map[i][j]; 29 30 memset(h, 0, sizeof(h)); 31 l[1] = 1, r[col] = col; 32 int t, ans = -1; 33 for(i = 1; i <= row; ++i) 34 { 35 for(j = 1; j <= col; ++j) 36 if(map[i][j] == 'F') 37 ++h[j]; 38 else 39 h[j] = 0; 40 41 for(j = 2; j <= col; ++j) 42 { 43 t = j; 44 while(t > 1 && h[j] <= h[t-1]) 45 t = l[t-1]; 46 l[j] = t; 47 } 48 for(j = col-1; j > 0; --j) 49 { 50 t = j; 51 while(t < col && h[j] <= h[t+1]) 52 t = r[t+1]; 53 r[j] = t; 54 } 55 for(j = 1; j <= col; ++j) 56 ans = max(ans, (r[j]-l[j]+1)*h[j]); 57 } 58 printf("%d ", ans * 3); 59 } 60 return 0; 61 }