Cod sursa(job #333620)

Utilizator hasegandaniHasegan Daniel hasegandani Data 23 iulie 2009 13:05:27
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 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];
                    }
                }
            else
                ss[i][j]==max(ss[i][j],max(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];
                    }
                } 
            else         
                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");
        }
     */       
    
    int max1,max2;
    for(int i=1;i<=n;++i)
        {
        max1=0; 
        max2=0;
        for(int j=1;j<=m;++j)
            {
            if (max1<ss[i][j])
                max1=ss[i][j];
                
            if (max2<sj[i+1][j])
                max2=sj[i+1][j];
            }
        if (Sol<max1+max2)
            Sol=max1+max2;
    //    printf("%d: %d %d\n",i,max1,max2);
        }
    printf("%d\n",Sol);
    
    return 0;
}