1.题目描述：点击打开链接
2.解题思路：本题利用扫描法解决：从上向下扫描每一行，如果我们把每个格子向上延伸的连续空格看做一条悬线，并用up(i,j),left(i,j),right(i,j)表示格子(i,j)的悬线长度以及该悬线向左，向右能够运动的“运动极限”，即最远能够走到哪一列。这样，每个格子(i,j)对应着一个以第i行为下边界，高度为up(i,j)，宽度为right(i,j)-left(i,j)的矩形，那么这些矩形中的面积最大值就是题目所求。因此，关键是如何快速的求出这三个数值。
当格子(i,j)不是空格时，3个数组的值均为0，否则up(i,j)=up(i-1,j)+1。同样可以找到left的递推公式：left(i,j)=max{left(i-1,j),lo+1}（lo表示第i行目前最近的障碍格的列编号）如果从左往右扫描，则很容易维护lo。right的算法类似，但需要从右往左扫描。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 1000int mat[N][N], up[N][N], Left[N][N], Right[N][N];int main(){//freopen("t.txt", "r", stdin);int T;cin >> T;while (T–){int m, n;cin >> m >> n;for (int i = 0; i < m;i++)for (int j = 0; j < n; j++){int ch = getchar();while (ch != 'F'&&ch != 'R')ch = getchar();mat[i][j] = ch == 'F' ? 0 : 1;}int ans = 0;for (int i = 0; i < m; i++)//从上到下逐行处理{int lo = -1, ro = n;for (int j = 0; j < n;j++)//从左到右扫描，维护up和leftif (mat[i][j] == 1)//有障碍物{up[i][j] = Left[i][j] = 0;lo = j;//第i行目前最近的障碍格的列编号}else{up[i][j] = i == 0 ? 1 : up[i – 1][j] + 1;//先判断，后赋值Left[i][j] = i == 0 ? lo + 1 : max(Left[i – 1][j], lo + 1);}for (int j = n – 1; j >= 0; j–)//从右往左扫描，维护right并更新答案if (mat[i][j] == 1){Right[i][j] = n;ro = j;}else{Right[i][j] = i == 0 ? ro – 1 : min(Right[i – 1][j], ro – 1);ans = max(ans, up[i][j] * (Right[i][j] – Left[i][j] + 1));}}printf("%d\n", ans * 3);}return 0;}
，我只愿，在你的理想和希望里能为你增加一点鼓励，
