悬线法 || BZOJ3039: 玉蟾宫 || Luogu P4147 玉蟾宫

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #define min(a,b) ((a)<(b)?(a):(b))
 5 #define max(a,b) ((a)>(b)?(a):(b))
 6 using namespace std;
 7 const int maxn=1050,maxm=maxn;
 8 int N,M,L[maxn][maxm],R[maxn][maxm],H[maxn][maxm],ans=0;
 9 char c,C[maxn][maxm];
10 int main(){
11     scanf("%d%d",&N,&M);
12     for(int i=1;i<=N;i++){
13         for(int j=1;j<=M;j++){
14             c=getchar();
15             while(c!='R'&&c!='F')c=getchar();
16             C[i][j]=c;
17         }
18     }
19     for(int i=1;i<=N;i++){
20         for(int j=1;j<=M;j++){
21             if(C[i][j]=='F')H[i][j]=H[i-1][j]+1;
22             else H[i][j]=0;
23             if(C[i][j]=='F')L[i][j]=L[i][j-1]+1;
24             else L[i][j]=0;
25             int r=M-j+1;
26             if(C[i][r]=='F')R[i][r]=R[i][r+1]+1;
27             else R[i][r]=0;
28         }
29     }
30     for(int i=1;i<=N;i++){
31         for(int j=1;j<=M;j++){
32             if(H[i][j]>1){
33                 L[i][j]=min(L[i][j],L[i-1][j]);
34                 R[i][j]=min(R[i][j],R[i-1][j]);
35             }
36             ans=max(ans,(L[i][j]+R[i][j]-1)*H[i][j]);
37         }
38     }
39     ans*=3;
40     printf("%d\n",ans);
41     return 0;
42 }