Cod sursa(job #1504638)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 17 octombrie 2015 23:41:45
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <cstdio>
#define NMAX 225
int a[NMAX],b[NMAX],c[NMAX];
int mat[NMAX][NMAX],sum[NMAX][NMAX],sum2[NMAX][NMAX];
int n,m;
int max(int a,int b)
{
    if(a<b) return b;
    return a;
}
int main()
{
    freopen ("bmatrix.in","r",stdin);
    freopen ("bmatrix.out","w",stdout);
    scanf("%d%d",&m,&n);
    char ch;
    for(int i=1;i<=m;i++)
    {
        scanf("%c",&ch);
        for(int j=1;j<=n;j++)
        {
            scanf("%c",&ch);
            mat[i][j]=ch-'0';
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            sum[j][i]=sum[j-1][i]+mat[j][i];
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++) sum2[i][j]=sum2[i][j-1]+mat[i][j];
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=i+1;j<=m;j++)
        {
            int dist=0;
            for(int k=1;k<=n;k++)
            {
                if(sum[j][k]-sum[i-1][k]==0)
                {
                    dist+=(j-i+1);
                    if(a[k]<dist) a[k]=dist;
                }
                else dist=0;
            }
        }
    }
    b[1]=a[1];
    a[1]=0;
    for(int i=2;i<=n;i++)
    {
        b[i]=max(a[i],b[i-1]);
        a[i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=i+1;j<=m;j++)
        {
            int dist=0;
            for(int k=n;k>=1;k--)
            {
                if(sum[j][k]-sum[i-1][k]==0)
                {
                    dist+=(j-i+1);
                    if(a[k]<dist) a[k]=dist;
                }
                else dist=0;
            }
        }
    }
    c[n]=a[n];
    for(int i=n-1;i>=1;i--) c[i]=max(a[i],c[i+1]);
    int maxim=0;
    for(int i=1;i<n;i++) maxim=max(maxim,b[i]+c[i+1]);
    for(int i=1;i<=n;i++)
    {
        a[i]=0;
        b[i]=0;
        c[i]=0;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int dist=0;
            for(int k=1;k<=m;k++)
            {
                if(sum2[k][j]-sum2[k][i-1]==0)
                {
                    dist+=(j-i+1);
                    if(a[k]<dist) a[k]=dist;
                }
                else dist=0;
            }
        }
    }
    b[1]=a[1];
    for(int i=2;i<=m;i++) b[i]=max(b[i-1],a[i]);
    for(int i=1;i<=m;i++) a[i]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int dist=0;
            for(int k=m;k>=1;k--)
            {
                if(sum2[k][j]-sum2[k][i-1]==0)
                {
                    dist+=(j-i+1);
                    if(a[k]<dist) a[k]=dist;
                }
                else dist=0;
            }
        }
    }
    c[m]=a[m];
    for(int i=m-1;i>=1;i--) c[i]=max(c[i+1],a[i]);
    for(int i=1;i<m;i++) maxim=max(maxim,b[i]+c[i+1]);
    printf("%d\n",maxim);
}