hdu 2870 Largest Submatrix

思路分析： 枚举a b c  然后用 hdu  1505  类似的方式求出最大的子矩阵。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n,m;
int map[1005][1005];
char save[1005][1005];
int l[1005];
int r[1005];

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        scanf("%s",save[i]+1);

        int ans=-1;
        for(int t=1;t<=3;t++)
        {
            memset(map,0,sizeof map);

            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(t==1){
                        if(save[i][j]==‘a‘ || save[i][j]==‘y‘ || save[i][j]==‘z‘ || save[i][j]==‘w‘)
                        map[i][j]=map[i-1][j]+1;
                        else map[i][j]=0;
                    }
                    else if(t==2)
                    {
                        if(save[i][j]==‘b‘ || save[i][j]==‘x‘ || save[i][j]==‘z‘ || save[i][j]==‘w‘)
                        map[i][j]=map[i-1][j]+1;
                        else map[i][j]=0;
                    }
                    else if(t==3)
                    {
                        if(save[i][j]==‘c‘ || save[i][j]==‘x‘ || save[i][j]==‘y‘ || save[i][j]==‘z‘)
                        map[i][j]=map[i-1][j]+1;
                        else map[i][j]=0;
                    }
                }

                l[1]=1;r[m]=m;
                map[i][0]=map[i][m+1]=-1;
                
                for(int j=2;j<=m;j++)
                {
                    l[j]=j;
                    while(map[i][j]<=map[i][l[j]-1])
                    l[j]=l[l[j]-1];
                }

                for(int j=m-1;j>=1;j--)
                {
                    r[j]=j;
                    while(map[i][j]<=map[i][r[j]+1])
                    r[j]=r[r[j]+1];
                }

                for(int j=1;j<=m;j++)
                {
                    ans=max(ans,(r[j]-l[j]+1)*map[i][j]);
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdu 2870 Largest Submatrix

原文：http://blog.csdn.net/u010709592/article/details/18796919