hdu 2870 Largest Submatrix(平面直方图的最大面积 变形)

#include <cstdio>
#include <map>
#include <iostream>
#include<cstring>
#include<bits/stdc++.h>
#define ll long long int
#define M 6
using namespace std;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1};
int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1};
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
char G[1007][1007];
int l[1007],r[1007];
int h[1007];
int m,n;
int main(){
    ios::sync_with_stdio(false);
    char t[3]={‘a‘,‘b‘,‘c‘};
    char equal[3][3]={‘b‘,‘c‘,‘x‘,‘a‘,‘c‘,‘y‘,‘a‘,‘b‘,‘w‘};
    while(cin>>m>>n){
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                cin>>G[i][j];
        int ans=-inf;
    for(int ii=m;ii>=1;ii--){ //遍历每一行 
        for(int i=0;i<3;i++){    //每一行都有‘a‘,‘b‘,‘c‘三种情况 
            char temp=t[i];
            memset(h,0,sizeof(h));
            memset(l,0,sizeof(l));
            memset(r,0,sizeof(r));
            for(int k=1;k<=n;k++)
                for(int j=ii;j>=1;j--){
                    if(G[j][k]==equal[i][0]||G[j][k]==equal[i][1]||G[j][k]==equal[i][2])
                    break;
                    h[k]++;    //记录该层的高度 
                }
            l[1]=1; r[n]=n;
            for(int k=2;k<=n;k++){
                int t=k;
                while(t>1&&h[k]<=h[t-1]){
                    t=l[t-1];
                }
                l[k]=t;
            }
            for(int k=n-1;k>=1;k--){
                int t=k;
                while(t<n&&h[k]<=h[t+1]){
                    t=r[t+1];
                }
                r[k]=t;
            }
            for(int k=1;k<=n;k++)
                ans=max(ans,h[k]*(r[k]-l[k]+1));
        }
    }
        cout<<ans<<endl;
    }
}