今日练习
LA 3029(HALF COPY);
LA 3695;
LA 3029
//
// Created by 21122 on 2022/6/2/0002.
//
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1005;
int arr[MAXN][MAXN];
int up_arr[MAXN][MAXN], left_arr[MAXN][MAXN], right_arr[MAXN][MAXN];
int main()
{
int T;
cin >> T;
while(T--)
{ // 一共 T 组数据;
int m, n;
char ch;
cin >> m >> n;
// 数据输入
for(int i = 1; i <=m ; i++)
{
for(int j = 1; j <= n; j++)
{
cin >>ch;
// F 空地记为1, R 障碍记为0;
arr[i][j] = (ch == 'F') ? 1 : 0;
}
}
int res = 0;
for(int i = 1;i <= m; i++)
{ // 自上而下,即行扫描
// left[][]、right[][] 分别为(i, j)处的竖线能够向左/右拓展到的 最远下标,
// 通过 lo、ro 来标记 BLOCK ;从而方便于求解 left 和 right
int lo = 0, ro = n + 1;
for(int j = 1; i <= n; j++)
{ // 从左到右, 修改left 和up
if(arr[i][j] == 0)
{ //Block
left_arr[i][j] = 0;
up_arr[i][j] = 0;
lo = j;
}
else
{ // 空地;
if(i == 1)
{
up_arr[i][j] = 0;
}
else
{
up_arr[i][j] = up_arr[i - 1][j] + 1;
}
if(i == 1)
{
left_arr[i][j] = lo + 1;
}
else
{
left_arr[i][j] = max(left_arr[i - 1][j], lo + 1);
}
}
}
for(int j = n; j >= 1; j--)
{ // 自右向左,同理
if(arr[i][j] == 1)
{
//up_arr[i][j] = 0;
right_arr[i][j] = n;
ro = j;
}
else
{
right_arr[i][j] = i == 0 ? ro - 1 : min(right_arr[i - 1][j], ro - 1);
res = max(res, up_arr[i][j] * (right_arr[i][j] - left_arr[i][j] + 1));
}
}
}
}
return 0;
}