Acwing 152. 城市游戏(暴力枚举平面 单调栈）

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
char s[N][N];
int a[N],ans=-1,l[N],r[N];
int get(int x){
    for(int i=1;i<=m;i++){
        int cnt=0,tep=x;
        while(tep>=1&&s[tep][i]=='F')cnt++,tep--;
        a[i]=cnt;
    }
    stack<int>s1,s2;
    a[0]=a[m+1]=-1;
    s1.push(0);
    for(int i=1;i<=m;i++){
        while(a[s1.top()]>=a[i])s1.pop();
        l[i]=s1.top();
        s1.push(i);
    }
    s2.push(m+1);
    for(int i=m;i>=1;i--){
        while(a[s2.top()]>=a[i])s2.pop();
        r[i]=s2.top();
        s2.push(i);
    }
    int maxx=-1;
    for(int i=1;i<=m;i++){
        maxx=max(maxx,a[i]*(r[i]-l[i]-1));
    }
    return maxx*3;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf(" %c",&s[i][j]);
        }
        
    }
    for(int i=1;i<=n;i++){
        //cout<<get(i)<<endl;
        ans=max(ans,get(i));
    }
    cout<<ans<<endl;
}