题意：给一个m*n的矩阵， 其中一些格子是空地（F）, 其他是障碍（R）。找一个全部由F
组成的面积最大的子矩阵， 输出其面积乘以3的结果。
思路：如果用枚举的方法，时间复杂度是O(m^2 n^2);
因为不但要枚举每一个点，而且矩阵的大小不知道，所以还要枚举长和宽。
可以通过枚举每一个点，求该点所能构成的最大矩形的边界。
分别用le[], rig[] 和 up[] 表示左边界，右边界和 上边界。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
#define LL long long
using namespace std;
const int maxn = +; int mat[maxn][maxn], up[maxn][maxn], le[maxn][maxn], rig[maxn][maxn];
int main()
{
int t, ans;
int m, n, i, j, lo, ro;
scanf("%d", &t);
while(t--)
{
ans = ;
scanf("%d%d", &m, &n);
for(i = ; i < m; i++)
for(j = ; j < n; j++)
{
char ch = getchar();
while(ch!='F'&&ch!='R')
ch = getchar();
mat[i][j] = ch == 'F' ?:;
}
for(i = ; i < m; i++)
{
lo = -; ro = n;
for(j = ; j < n; j++) //顺着求上边界和左边界
if(mat[i][j] == ) { up[i][j] = le[i][j] = ; lo = j; }
else
{
up[i][j] = i == ?:up[i-][j] + ; //高度直接加
le[i][j] = i == ? lo+ : max(le[i-][j], lo+);//左边界需要当前行和上一行的限制
} for(j = n-; j >= ; j--) //从n-1求右边界
if(mat[i][j] == )
{
rig[i][j] = n; ro = j;
}
else
{
rig[i][j] = i == ? ro- : min(rig[i-][j], ro-);
ans = max(ans, up[i][j]*(rig[i][j]-le[i][j]+)); //求子矩阵的面积
}
}
printf("%d\n", ans*);
}
return ;
}