题意：给一个m*n的矩阵， 其中一些格子是空地（F）, 其他是障碍（R）。找一个全部由F
组成的面积最大的子矩阵， 输出其面积乘以3的结果。
思路：如果用枚举的方法，时间复杂度是O(m^2 n^2);
因为不但要枚举每一个点，而且矩阵的大小不知道，所以还要枚举长和宽。
可以通过枚举每一个点，求该点所能构成的最大矩形的边界。
分别用le[], rig[] 和 up[] 表示左边界，右边界和 上边界。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstdio> 6 #include <vector> 7 #include <algorithm> 8 #define LL long long 9 using namespace std; 10 const int maxn = 1000+10; 11 12 int mat[maxn][maxn], up[maxn][maxn], le[maxn][maxn], rig[maxn][maxn]; 13 int main() 14 { 15 int t, ans; 16 int m, n, i, j, lo, ro; 17 scanf("%d", &t); 18 while(t--) 19 { 20 ans = 0; 21 scanf("%d%d", &m, &n); 22 for(i = 0; i < m; i++) 23 for(j = 0; j < n; j++) 24 { 25 char ch = getchar(); 26 while(ch!='F'&&ch!='R') 27 ch = getchar(); 28 mat[i][j] = ch == 'F' ?0:1; 29 } 30 for(i = 0; i < m; i++) 31 { 32 lo = -1; ro = n; 33 for(j = 0; j < n; j++) //顺着求上边界和左边界 34 if(mat[i][j] == 1) { up[i][j] = le[i][j] = 0; lo = j; } 35 else 36 { 37 up[i][j] = i == 0?1:up[i-1][j] + 1; //高度直接加 38 le[i][j] = i == 0 ? lo+1 : max(le[i-1][j], lo+1);//左边界需要当前行和上一行的限制 39 } 40 41 for(j = n-1; j >= 0; j--) //从n-1求右边界 42 if(mat[i][j] == 1) 43 { 44 rig[i][j] = n; ro = j; 45 } 46 else 47 { 48 rig[i][j] = i ==0 ? ro-1 : min(rig[i-1][j], ro-1); 49 ans = max(ans, up[i][j]*(rig[i][j]-le[i][j]+1)); //求子矩阵的面积 50 } 51 } 52 printf("%d ", ans*3); 53 } 54 return 0; 55 }