Cod sursa(job #29053)

Utilizator devilkindSavin Tiberiu devilkind Data 8 martie 2007 15:56:49
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <stdio.h>
#define NMAX 201

FILE *f = fopen("bmatrix.in","rt"), *g = fopen("bmatrix.out","wt");

long int a[NMAX][NMAX],sc[NMAX][NMAX],sl[NMAX][NMAX];
long int n,m,i,j,k,max,shs[NMAX],svs[NMAX],x,shd[NMAX],svd[NMAX],l;


void citire()
{
char c[NMAX];
fscanf(f,"%ld %ld\n",&n,&m);

for (i=1;i<=n;i++)
    {
    fgets(c,NMAX,f);
    for (j=1;j<=m;j++)
        {
        a[i][j]=(long int) c[j-1] - 48;
        sc[i][j]=sc[i-1][j]+a[i][j];
        sl[i][j]=sl[i][j-1]+a[i][j];
	}
    fscanf(f,"\n");
    }
}

void vert()
{
for (i=1;i<=n;i++)
    for (j=i;j<=n;j++)
        {
        l=0;
        max=0;
        for (k=1;k<=m;k++)
            {
            x=sc[j][k]-sc[i-1][k];
	    if (x==0) l+=j-i+1;
               else l=0;
            if (l>max) max=l;
	    if (max>shs[k]) shs[k]=max;
            }
        l=0;
        max=0;
        for (k=m;k>=1;k--)
            {
            x=sc[j][k]-sc[i-1][k];
	    if (x==0) l+=j-i+1;
               else l=0;
            if (l>max) max=l;
	    if (max>shd[k]) shd[k]=max;
            }
        }     
}

void horiznt()
{
for (i=1;i<=m;i++)
    for (j=i;j<=m;j++)
        {
        l=0;
        max=0;
        for (k=1;k<=n;k++)
            {
	    x=sl[k][j]-sl[k][i-1];
	    if (x==0) l+=j-i+1;
	       else l=0;
	    if (l>max) max=l;
	    if (max>svs[k]) svs[k]=max;
	    }
	l=0;
	max=0;
	for (k=n;k>=1;k--)
	    {
	    x=sl[k][j]-sl[k][i-1];
	    if (x==0) l+=j-i+1;
	       else l=0;
	    if (l>max) max=l;
	    if (max>svd[k]) svd[k]=max;
	    }
	}
     
     
}


void solve()
{
vert();
horiznt();
max=0;
for (i=1;i<n;i++)
    if (shs[i]+shd[i+1]>max) max=shs[i]+shd[i+1]; 

for (i=1;i<=m;i++)
    if (svs[i]+svd[i+1]>max) max=svs[i]+svd[i+1]; 
    
fprintf(g,"%ld",max);
}
    

int main()
{
citire();
solve();
fclose(f);
fclose(g);
return 0;
}