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;

	}