今日练习

今日练习

LA 3029(HALF COPY);

LA 3695;

LA 3029

image-20220604021817437

//
// 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;
}