Cod sursa(job #461150)

Utilizator edp100Edp100 edp100 Data 5 iunie 2010 18:52:08
Problema BMatrix Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include<stdio.h>
#include<string.h>
#define maxim(a,b) (a>b ? a : b)

int up[205], down[205];
int n,m,vf,st[205],p[205];
int a[205][205],b[205][205];
int lf[205],rt[205];

void calcul(int a[][205], int *d, int l,int c)
{
	int i,j;
	memset(p,0,sizeof(p));
	for(i=1;i<=l;i++)
	{
		for(j=1;j<=c;j++)
			if(a[i][j])
				p[j]=0;
			else
				p[j]++;
		for(j=1,st[vf=0]=0;j<=c;j++)
		{
			while(vf>=1 && p[st[vf]]>=p[j])
				vf--;
			lf[j]=st[vf];				
			st[++vf]=j;		
		}	
		for(j=c,st[vf=0]=c+1;j>=1;j--)
		{
			while(vf>=1 && p[st[vf]]>=p[j])
				vf--;
			rt[j]=st[vf];	
			st[++vf]=j;		
		}
		d[i]=d[i-1];
		for(j=1;j<=c;j++)
			d[i]=maxim(d[i],(rt[j]-lf[j]-1)*p[j]);
	}
}

int horiz(int a[][205], int l, int c)
{
	int i,j,aux;
	
	memset(up,0,sizeof(up));
	memset(down,0,sizeof(down));
	
	calcul(a, up, l, c);
	for(i=1;i<=l;i++)
		for(j=1;j<=c;j++)
			b[l-i+1][j]=a[i][j];	
	calcul(b, down, l, c);
	
	for (i=1,j=l;i<j;i++,j--)
	{
		aux=down[i];
		down[i]=down[j];
		down[j]=aux;
	}
	
	int sol=0;
	for (i=1;i<=l;i++)
		sol=maxim(sol, up[i]+down[i+1]);
	return sol;
}

int main ()
{
	char ch;
	int i,j;
	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);
			a[i][j]=ch-'0';
		}	
		scanf("\n");	
	}
	
	int h = horiz(a, n, m);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			b[j][i]=a[i][j];
	int v = horiz(b, m, n);	

	printf("%d\n", maxim(h, v));
	
	return 0;
}