Cod sursa(job #3981)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 29 decembrie 2006 21:51:01
Problema BMatrix Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 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) {

		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]*(aux-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;

			//for (k=1;k<=st[0];k++) printf("%i ",st[k]);
			//printf("\n");	
		}
		
		//for (j=1;j<=m;++j) printf("%i ",p[j]);
		
		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]*(st[0]-j+1)>best) best=st[j]*(st[0]-j+1);
			
			if (st[j]*(p[st[0]]-p[j]+1)>best) best=st[j]*(p[st[0]]-p[j]+1);

		}

		//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;
}