P4147 玉蟾宫

时间:2022-01-06 02:36:20

P4147 玉蟾宫

给定一个 \(N * M\) 的矩阵

求最大的全为 \(F\) 的子矩阵

Solution

悬线法

限制条件为转移来的和现在的都为 \(F\)

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
#define LL long long
#define REP(i, x, y) for(int i = (x);i <= (y);i++)
using namespace std;
int RD(){
int out = 0,flag = 1;char c = getchar();
while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
return flag * out;
}
const int maxn = 2019;
int lenx, leny;
int map[maxn][maxn];
int l[maxn][maxn], r[maxn][maxn];
int up[maxn][maxn];
int ans;
void init(){
lenx = RD(), leny = RD();
REP(i, 1, lenx)REP(j, 1, leny){
char s[19];
scanf("%s", s);
if(s[0] == 'F'){
map[i][j] = 1;
l[i][j] = r[i][j] = j;
up[i][j] = 1;
}
}
REP(i, 1, lenx)REP(j, 2, leny){
if(map[i][j] && map[i][j - 1])l[i][j] = l[i][j - 1];
}
REP(i, 1, lenx)for(int j = leny - 1;j >= 1;j--){
if(map[i][j] && map[i][j + 1])r[i][j] = r[i][j + 1];
}
}
void solve(){
REP(i, 1, lenx)REP(j, 1, leny){
if(!map[i][j])continue;
if(i > 1 && map[i - 1][j]){
l[i][j] = max(l[i][j], l[i - 1][j]);
r[i][j] = min(r[i][j], r[i - 1][j]);
up[i][j] = up[i - 1][j] + 1;
}
int a = r[i][j] - l[i][j] + 1;
ans = max(ans, a * up[i][j]);
}
printf("%d\n", ans * 3);
}
int main(){
init();
solve();
return 0;
}