Cod sursa(job #64787)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 5 iunie 2007 17:36:27
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <stdio.h>
#define fin  "bmatrix.in"
#define fout "bmatrix.out"
#define Nmax 211

#define minf(a,b) ( (a)<(b)?(a):(b) )

int N,M,ret,bst1[Nmax],bst2[Nmax];
char map[Nmax][Nmax];


void go(int a[Nmax],int b[Nmax]) {
int i,j,k,vf,v[Nmax];
int len;
	for (i=0;i<Nmax;++i) 
		v[i]=a[i]=b[i]=0;
	
	for (i=1;i<=N;++i) 
	for (j=1,vf=0;j<=M;++j) {
		if (map[i][j]=='0')
			++v[j];
		else
			v[j]=0;
		for (len=v[j],k=j;k>0;--k) {
			len=minf(len,v[k]);
			if ( len * (j-k+1) > a[j] )
				a[j] = len*(j-k+1);
		}

		if ( a[j] < a[j-1] )
			a[j]=a[j-1];
	}

	for (i=0;i<Nmax;++i)
		v[i]=0;

	for (i=1;i<=N;++i) 
	for (j=M,vf=0;j>0;--j) {
		if (map[i][j]=='0')
			++v[j];
		else
			v[j]=0;
		for (len=v[j],k=j;k<=M;++k) {
			len=minf(len,v[k]);
			if ( len * (k-j+1) > b[j] )
				b[j] = len*(k-j+1);
		}

		if ( b[j] < b[j+1] )
			b[j]=b[j+1];
	}

}

void inv(char map[Nmax][Nmax],int &N,int &M) {
int i,j;
char aux[Nmax][Nmax];
	for (i=1;i<=N;++i)
	for (j=1;j<=M;++j)
		aux[j][N-i+1]=map[i][j];
	N+=M; M=N-M; N-=M; 
	for (i=1;i<=N;++i)
	for (j=1;j<=M;++j)
		map[i][j]=aux[i][j];
}

int main() {
int i,j;
	freopen(fin,"r",stdin); freopen(fout,"w",stdout);

	scanf("%d%d",&N,&M);

	for (i=1;i<=N;++i) {
		fgetc(stdin);
		for (j=1;j<=M;++j)
			map[i][j]=fgetc(stdin);
	}

	go(bst1,bst2);
	for (i=2;i<=M;++i)
		if ( bst1[i-1] + bst2[i] > ret && bst1[i-1] && bst2[i])
			ret=bst1[i-1]+bst2[i];
	
	inv(map,N,M);

	go(bst1,bst2);
	for (i=2;i<=M;++i) 
		if ( bst1[i-1] + bst2[i] > ret && bst1[i-1] && bst2[i])
			ret=bst1[i-1]+bst2[i];
	
	printf("%d\n",ret);

	return 0;
}