Cod sursa(job #333623)

Utilizator hasegandaniHasegan Daniel hasegandani Data 23 iulie 2009 13:13:14
Problema BMatrix Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include<stdio.h>

#define nmax 256
#define inf 0x3f3f3f

int n,m,vs[nmax][nmax],vj[nmax][nmax],ss[nmax][nmax],sj[nmax][nmax],Sol;
char a[nmax][nmax];

int max(int x,int y)
{
    if (x>y)
        return x;
    return y;
}

int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i)
        scanf("%s",a[i]);
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            {
            if (a[i][j]=='0')
                {
                vs[i][j]=vs[i][j-1]+1;
                int min=vs[i][j];
                if (ss[i][j]<min)
                    ss[i][j]=min;
                for(int k=i-1;k>=0 && vs[k][j];--k)
                    {
                    if (ss[i][j]<min*(i-k+1))
                        ss[i][j]=min*(i-k+1);
                    if (min>vs[k][j])
                        min=vs[k][j];
                    }
                }
            ss[i][j]=max(max(ss[i][j],ss[i-1][j]),ss[i][j-1]);
            }
    
    for(int i=n-1;i>=0;--i)
        for(int j=m-1;j>=0;--j)
            {
            if (a[i][j]=='0')
                {
                vj[i][j]=vj[i][j+1]+1;
                int min=vj[i][j];
                if (sj[i][j]<min)
                    sj[i][j]=min;
                for(int k=i+1;k<n && vj[k][j];++k)
                    {
                    if (sj[i][j]<min*(k-i+1))
                        sj[i][j]=min*(k-i+1);
                    if (min>vj[k][j])
                        min=vj[k][j];
                    }
                }        
            sj[i][j]=max(sj[i][j],max(sj[i+1][j],sj[i][j+1]));
            }
          /*
    for(int i=0;i<n;++i)
        {
        for(int j=0;j<m;++j)
            printf("%d ",ss[i][j]);
        printf("\n");
        }
    for(int i=0;i<n;++i)
        {
        for(int j=0;j<m;++j)
            printf("%d ",sj[i][j]);
        printf("\n");
        }
           */
    
    for(int i=0;i<n;++i)
        {
        if (Sol<ss[i][m-1]+sj[i+1][0])
            Sol=ss[i][m-1]+sj[i+1][0];
       // printf("%d: %d %d\n",i,max1,max2);
        }
    printf("%d\n",Sol);
    
    return 0;
}