Cod sursa(job #191038)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 25 mai 2008 00:04:36
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 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(i=1;i<=n;++i)
	{
		for(j=1;j<=m;++j)
			printf("%d ",mat[i][j]);
		printf("\n");
	}*/	
	
	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;
				//printf(" %d %d %d %d\n",p,i,j,min); 
				if(p>rez)  
				{
					rez=p;
					
					x=i-min+1;
					y=j-nr+1;
					xx=i;
					yy=j;
					//printf("%d %d %d %d %d\n",rez,x,y,xx,yy);
				}					
			}
		}
		
	/*for(i=1;i<=n;++i) 
	{
		printf("\n");
		for(j=1;j<=m;++j)
			printf(" %d", mat[i][j]); 
	} */	
		
	//printf("\n %d %d %d %d\n",x,y,xx,yy);
	
	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) 
	{
		printf("\n");
		for(j=1;j<=m;++j)
			printf(" %d", mat[i][j]); 
	} */
	
	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;
}