二维图中找最大子矩形的四道题

hdu 1506 直方图中找最大矩形

找出每个矩形以自己的高能延伸到的左右边界

#include<stdio.h>#include<string.h>#include<stdlib.h>#define maxn 1015int n,m,max;char ma[maxn][maxn];int map[maxn][maxn];int dp[maxn];int cmp(const void*a,const void*b){    //return *(int*)a>*(int*)b?1:-1;    return *(int*)a-*(int*)b;}int main(){    int i,j,k,l;    while(~scanf("%d %d",&n,&m)&&n&&m)    {        for(i=0;i<n;i++)        {            scanf("%s",&ma[i]);        }        memset(map,0,sizeof(map));                for(i=0;i<n;i++)        {            for(j=0;j<m;j++)                if(ma[i][j]=='1')                    map[i][j]=1;        }        max=-1;        int tmp;        for(i=0;i<n;i++)        {            memset(dp,0,sizeof(dp));            for(j=0;j<m;j++)            {                for(k=i;k>=0;k--)                {                    if(map[k][j]==1)                        dp[j]++;                    else                        break;                }            }            qsort(dp,m,sizeof(int),cmp);            for(l=0;l<m;l++)            {                tmp=dp[l]*(m-l);                if(tmp>max)                    max=tmp;            }        }        printf("%d\n",max);    }    return 0;}