Input
The rst line of the input le contains an integer K | determining the number of datasets. Next lines
contain the area descriptions. One description is dened in the following way: The rst line contains
two integers-area length M ≤ 1000 and width N ≤ 1000, separated by a blank space. The next M
lines contain N symbols that mark the reserved or free grid units, separated by a blank space. The
symbols used are:
R - reserved unit
F - free unit
In the end of each area description there is a separating line.
Output
For each data set in the input le print on a separate line, on the standard output, the integer that
represents the prot obtained by erecting the largest building in the area encoded by the data set.
Sample Input
2
5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F
5 5
R R R R R
R R R R R
R R R R R
R R R R R
R R R R R
Sample Output
45
0
1.如何拆分最大矩形，遍历所有点的上左右边界，在遍历中求最大值
2.颠倒看数组都是一样的
#include <cstdio>
#include <algorithm>
#include <iostream> #define MAX 1000 using namespace std;
int A[MAX][MAX], up[MAX][MAX], l[MAX][MAX], r[MAX][MAX], m, n, T; int main() {
cin >> T;
while (T--) {
cin >> m >> n;
for (int i = , c; i < m; ++i) {
for (int j = ; j < n; ++j) {
do { c = getchar(); }
while (c != 'F' && c != 'R');
A[i][j] = c == 'F';
}
}
int ans = ;
for (int i = ; i < m; ++i) {
for (int j = , lo = ; j < n; ++j) {
if (!A[i][j]) {
up[i][j] = l[i][j] = ; //把l设到最左，方便上方的点求lo
lo = j + ;
} else {
up[i][j] = i == ? : up[i - ][j] + ;
l[i][j] = i == ? lo : max(l[i - ][j], lo);
}
} for (int j = n - , ro = n; j >= ; --j) {
if (!A[i][j]) {
r[i][j] = n, ro = j;
} else {
r[i][j] = i == ? ro : min(r[i - ][j], ro);
ans = max(ans, up[i][j] * (r[i][j] - l[i][j])); //在求右边界时同时求矩形面积最大值
}
}
}
cout << ans * << endl;
}
}