P3135题解

Nephren_Sakura · 2023-03-02 09:41:28 · 题解

首先，我们可以考虑暴力枚举出来矩阵的最左方在那一列和最右方在哪一列。

然后考虑枚举行，设当前行为 i。

显然可以预处理前缀和求出每一行的每一段区间有多少个沼泽地。

然后，因为我们要求面积最大，所以我们维护一个 last 表示满足条件的不超过 i 的与 i 距离最远的行。（这句话可能有点绕，请好好理解）

设最左列为 l，最右列为 r。

分情况讨论：

1. 若 c_{i,l} 为沼泽地或 c_{i,r} 为沼泽地，显然在 i 上方的所有 last 都不满足条件，先将 last=i+1，然后继续往下找直到找到一个满足条件的 last。

2. 若第 i 行的 l 列到 r 列之间都没有沼泽地，更新答案。

3. 否则不做任何操作。

下面给出代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,sum[205][205],maxi=0;
char c[205][205];
bool check(int h,int l,int r){
    return sum[h][r]-sum[h][l-1]==0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>c[i][j];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            sum[i][j]=sum[i][j-1]+(c[i][j]=='X');
    for(int l=1; l<=m; l++){
        for(int r=l; r<=m; r++){
            int last=1,mx=0;
            for(int i=1; i<=n; i++){
                if(c[i][l]=='X'||c[i][r]=='X'){
                    last=i+1;
                    continue;
                }
                while(check(last,l,r)==false)
                    last++;
                if(check(i,l,r)==true)
                    mx=max(mx,i-last+1);
            }
            maxi=max(maxi,(r-l+1)*mx);
        }
    }
    cout<<maxi;
    return 0;
}