Cod sursa(job #319307)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 31 mai 2009 13:02:38
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>
#define N 512
char ch,a[N][N];
int mat[N][N];
int main()
{

    int min,p,rez=0,rez2=0,nr,n,m,i,j,h;
    freopen("bmatrix.in", "r",stdin);
    freopen("bmatrix.out", "w",stdout);
    scanf("%d%d\n", &n,&m);
    for(i=1;i<=n;++i)
    {
	for(j=1;j<=m;++j)
	{
	    scanf("%c", &ch);
	    if(ch=='0')
		a[i][j]=1;
	    else
		a[i][j]=0;
	}
	scanf("%c", &ch);
    }

    for(j=1;j<=m;++j)
    {
	nr=0;
	for(i=1;i<=n;++i)
	if(a[i][j]==1)
	    mat[i][j]=++nr;
	else
	{
	    mat[i][j]=0;
	    nr=0;
	}
    }

    int x,y,xx,yy;

    for(i=1;i<=n;++i)
	for(h=1;h<=m;++h)
	{
	    nr=0; min=mat[i][h];
	    for(j=h;j<=m;++j)
	    {
		++nr;
		if(mat[i][j]<min)
		    min=mat[i][j];
		if(!mat[i][j])
		{
		    min=3;
		    nr=0;
		}
		p=min*nr;
		if(p>rez)
		{
		    rez=p;

		    x=i-min+1;
		    y=j-nr+1;
		    xx=i;
		    yy=j;
		}
	    }
	}


    for(int i=x;i<=xx;++i)
	for(int j=y;j<=yy;++j)
	    a[i][j]=0;

    for(j=1;j<=m;++j)
    {
	nr=0;
	for(i=1;i<=n;++i)
	if(a[i][j]==1)
	    mat[i][j]=++nr;
	else
	{
	    mat[i][j]=0;
	    nr=0;
	}
    }


    for(i=1;i<=n;++i)
	for(h=1;h<=m;++h)
	{
	    nr=0; min=mat[i][h];
	    for(j=h;j<=m;++j)
	    {
		++nr;
		if(mat[i][j]<min)
		    min=mat[i][j];
		if(!mat[i][j])
		{
		    min=3;
		    nr=0;
		}
		p=min*nr;
		if(p>rez2)
		    rez2=p;
	    }
	}


    printf("%d\n", rez+rez2);


    return 0;
}