152. 城市游戏【单调栈】

131. 直方图中最大的矩形 这一道题的变种。

我们只多了枚举所有的地面

#include
using namespace std;
const int N=1010;
int s[N][N],a[N],n,m;
char c[N][N];
int solve(int x)
{
    for(int i=1;i<=m;i++) a[i]=s[x][i];
    int lmin[N]={0},rmin[N]={0};
    a[0]=-1,a[m+1]=-1;
    stack<int>st; st.push(0);
    for(int i=1;i<=m;i++)
    {
        while(st.size()&&a[st.top()]>=a[i]) st.pop();
        lmin[i]=st.top();
        st.push(i);
    }
    while(st.size()) st.pop();
    st.push({m+1});
    for(int i=m;i>=1;i--)
    {
        while(st.size()&&a[st.top()]>=a[i]) st.pop();
        rmin[i]=st.top();
        st.push(i);
    }
    int ans=0;
    for(int i=1;i<=m;i++) ans=max(ans,a[i]*(rmin[i]-lmin[i]-1));
    return ans;
}
int main(void)
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>c[i][j];
            if(c[i][j]=='F') s[i][j]=s[i-1][j]+1;
            else s[i][j]=0;
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,solve(i));//枚举所有的地面
    cout<<res*3<<endl;
    return 0;
}