Cod sursa(job #4078)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 30 decembrie 2006 11:18:28
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb

#include<stdio.h>
#define fin "bmatrix.in"
#define fout "bmatrix.out"
#define NMAX 201
int n,m,sol,map[NMAX][NMAX];
FILE *in,*out;

int count(int lb,int le,int cb,int ce) {
int i,j,k,best=0,st[NMAX],p[NMAX],tmp[NMAX]={0},aux;
	
	for (i=lb;i<=le;++i) {

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

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

			else aux=0;		
					
			tmp[j]=aux;
		
		}

		for (j=cb;j<=ce;++j) { 

			k=j-1;
			while (tmp[j]<=tmp[k] && k>=cb) --k;

			aux=(j-k);
			
			k=j+1;
			while (tmp[j]<=tmp[k] && k<=ce) ++k;

			aux+=(k-j-1);

			if (tmp[j]*aux>best) best=tmp[j]*aux;
		//printf(" best: %i\n",best);
		}
	
	}
	
	return best;
	
}

int main() {
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;
	}
	
	//sol=count(1,n,1,m);
		
	//for (i=1;i<=n;++i) { printf("\n");
	//	for (j=1;j<=m;++j) printf("%i",map[i][j]);}
	fprintf(out,"%i\n",sol);	
	
	fclose(in); fclose(out);

	return 0;
}