Cod sursa(job #4097)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 30 decembrie 2006 12:44:57
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include<stdio.h>
#define fin "bmatrix.in"
#define fout "bmatrix.out"
#define NMAX 201
int n,m,sol,st[256],p[256],tmp[256],map[256][256];
FILE *in,*out;

int count(int lb,int le,int cb,int ce) {
register int i,j,k,best=0,aux;
	
	for (i=1;i<=m;++i) tmp[i]=0;

	for (i=lb;i<=le;++i) {

		st[0]=0;
		
		for (j=cb;j<=ce;++j) {
			
			aux=tmp[j];

			if (!map[i][j]) aux++;

			else aux=0;		
					
			tmp[j]=aux;
			
			st[++st[0]]=aux;
			
			p[st[0]]=j;

			k=st[0]; aux=st[0];
					
			while (k>1 && st[k-1]>st[k]) {
				
				--k;

				if (st[k]*(p[aux]-p[k])>best) best=st[k]*(p[aux]-p[k]);
				
				st[k]=st[k+1];	
			}
			
			if (tmp[j]*(p[st[0]]-p[k]+1)>best) best=tmp[j]*(p[st[0]]-p[k]+1);

			st[0]=k;

		}
		
		aux=1; 

		for (j=1;j<=st[0];++j) {
			
			if (st[j]==st[j-1] && j>1) ++aux;	
			
			else aux=1;

			if (st[j]*aux>best) best=st[j]*aux;

			if (st[j]*(p[st[0]]-p[j]+1)>best) best=st[j]*(p[st[0]]-p[j]+1);

		}

	}
	
	return best;
	
}

int main() {
register int i,j,best1,best2;
	
	in=fopen(fin,"r"); out=fopen(fout,"w");

	fscanf(in,"%i%i",&n,&m);

	for (i=1;i<=n;++i) {
		
		fgetc(in);

		for (j=1;j<=m;++j) 
			
			map[i][j]=(int)(fgetc(in)-'0');	
			
	}

	for (i=1;i<n;++i) { 
		
		best1=count(1,i,1,m);
		best2=count(i+1,n,1,m);

		if (best1+best2>sol) 
			
			sol=best1+best2;
	}

	for (j=1;j<m;++j) {
		
		best1=count(1,n,1,j);
		best2=count(1,n,j+1,m);

		if (best1+best2>sol) 
			
			sol=best1+best2;
	}
	
	fprintf(out,"%i\n",sol);	
	
	fclose(in); fclose(out);

	return 0;
}