Cod sursa(job #590587)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 18 mai 2011 17:19:49
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<stdio.h>

#define maxN 205

FILE*f=fopen("bmatrix.in","r");
FILE*g=fopen("bmatrix.out","w");

int n,m,i,j,D[maxN][maxN],Sol;
int vf,St[maxN],arie,Drept[4][maxN];
char A[maxN][maxN],Cpy[maxN][maxN];

void findmax ( char A[maxN][maxN] , int M[maxN] ){
	
	int i,j,p;
	
	for ( i = 1 ; i <= n ; ++i ){
		for ( j = 1 ; j <= m ; ++j ){
			if ( A[i][j] ){
				D[i][j] = 0;
			}
			else
				D[i][j] = D[i-1][j] + 1;
		}
	}
	
	for ( i = 1 ; i <= n ; ++i ){
		M[i] = M[i-1];
		
		for ( j = 1 , vf = 0 ; j <= m ; ++j ){
			p = St[vf];
			
			while ( vf && D[i][j] < D[i][ St[vf] ] ){
				arie = D[i][ St[vf] ] * ( p - St[vf-1] );
				M[i] = M[i] > arie ? M[i] : arie;
				--vf;
			}
			
			St[++vf] = j;
		}
		
		for ( p = St[vf] ; vf ; --vf ){
			arie = D[i][ St[vf] ] * ( p - St[vf-1] );
			M[i] = M[i] > arie ? M[i] : arie;
		}
		
	}
	
}

void rotate_right( char A[maxN][maxN] ){
	int i,j;
	
	for ( i = 1 ; i <= n ; ++i ){
		for ( j = 1 ; j <= m ; ++j ){
			Cpy[i][j] = A[i][j];
			A[i][j] = 0;
		}
	}
	
	for ( i = 1 ; i <= n ; ++i ){
		for ( j = 1 ; j <= m ; ++j ){
			A[j][n - i + 1] = Cpy[i][j];
		}
	}
	
	
}

inline void swap( int &a, int &b ){
	int aux = a;
	a = b;
	b = aux;
}

inline void solve () {
	
	int i,j;
	
	for ( i = 1; i < n ; ++i ){
		if ( Drept[0][i] + Drept[2][n-i] > Sol ){
			Sol = Drept[0][i] + Drept[2][n-i];
		}
	}
	
	for ( j = 1 ; j < m ; ++j ){
		if ( Drept[1][j] + Drept[3][m-j] > Sol ){
			Sol = Drept[1][j] + Drept[3][m-j];
		}
	}
	
	fprintf(g,"%d\n",Sol);
}


int main () {
	
	fscanf(f,"%d %d",&n,&m);
	
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%s",A[i]+1);
		for ( j = 1 ; j <= m ; ++j )
			A[i][j] -= '0';
	}
	
	for ( i = 0 ; i < 4 ; ++i ){
		findmax(A,Drept[i]);
		rotate_right(A);
		swap(n,m);
	}
	
	solve();
	
	fclose(f);
	fclose(g);
	
	return 0;
}