Cod sursa(job #333612)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 23 iulie 2009 12:55:12
Problema BMatrix Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<stdio.h>
#define DIM 201
int a[DIM][DIM],b[DIM][DIM],n,m;
int solve (int x1,int y1,int x2,int y2)
{
    int i,j,d1=0,d2=0,d3=0,max=0;
    for(i=x1;i<=x2;++i)
        for(j=y1;j<=y2;++j)
        {
            d1=b[i-1][j-1];
            d2=b[i-1][j];
            d3=b[i][j-1];
            if(a[i-1][j-1]==-1 || i==x1 || j==y1)
                d1=0;
            if(a[i-1][j]==-1 || i==x1)
                d2=0;
            if(a[i][j-1]==-1 || j==y1)
                d3=0;
            if(a[i][j]==-1)
                b[i][j]=-1;
            else
                b[i][j]=d2+d3+1-d1;
            if(max<b[i][j])
                max=b[i][j];            
        }
    return max;
    
}
void refresh ()
{
    int i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            b[i][j]=a[i][j];
}
int main ()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    int i,j,max=0,sum;
    char ch;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
    {
        scanf("\n");
        for(j=1;j<=m;++j)
        {
            scanf("%c",&ch);
            if(ch=='0')
                a[i][j]=0;
            else
                a[i][j]=-1;
        }
    }
    for(i=1;i<n;++i)
    {
        refresh ();
        sum=solve(1,1,n-i,m)+solve(n-i+1,1,n,m);
        if(max<sum)
            max=sum;
    }
    for(i=1;i<m;++i)
    {
        refresh ();
        sum=solve(1,1,n,m-1)+solve(1,m-i+1,n,m);
        if(max<sum)
            max=sum;
    }
    printf("%d",max);
    return 0;
}