Cod sursa(job #325429)

Utilizator c912045Marcu Florian c912045 Data 20 iunie 2009 15:29:49
Problema BMatrix Scor 40
Compilator cpp Status done
Runda Problemiada - Editia 5 Marime 1.47 kb
using namespace std;
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX_N 203
bool A[MAX_N][MAX_N];
int N,M;
inline int drept_max(int l1, int l2, int c1, int c2)
{
	int h[MAX_N], p = 0; // cate 0-uri am pe coloana i
	int L[MAX_N][MAX_N], l[MAX_N][MAX_N];
	int arie = 0;
	int i,j;
	memset(h,0,sizeof(h));
	for(i=l1;i<=l2;++i) for(j=c1;j<=c2;++j) L[i][j] = l[i][j] = 0;
	for(i=l1;i<=l2;++i)
		for(j=c1, p = 0;j<=c2;++j)
		{
			if(A[i][j] == 1) { h[j] = 0; p = 0; continue; }
			++p; h[j]++; 
			if(A[i-1][j-1] == 1)
			{
				if( h[j] > p ) { L[i][j] = h[j]; l[i][j] = 1; }
				else { L[i][j] = 1; l[i][j] = p; }
				arie = max(arie, L[i][j] * l[i][j]); 
				continue;
			}			
			arie = max(arie, max(h[j],p));
			L[i][j] = min(h[j], L[i-1][j-1] + 1);
			l[i][j] = min(p, l[i-1][j-1] + 1);
			if(j == 1) L[i][j] = h[j];
			if(i == 1) l[i][j] = p;
			arie = max(arie, L[i][j] * l[i][j]); 
		}
	return arie;
}
int Amax;
int main()
{
	freopen("bmatrix.in","r",stdin);
	freopen("bmatrix.out","w",stdout);
	scanf("%d %d\n",&N,&M);
	int i,j,a1,a2; char x;
	for(i=1;i<=N;++i)
	{
		for(j=1;j<=M;++j)
		{
			scanf("%c",&x);
			A[i][j] = x - '0';
		}
		scanf("\n");
	}
	for(i = 2; i < N; ++i)
	{
		a1 = drept_max(1,i,1,M);
		a2 = drept_max(i+1,N,1,M);
		Amax = max(Amax,a1+a2);
	}
	for(i = 2; i< M; ++i)
	{
		a1 = drept_max(1,N, 1, i);
		a2 = drept_max(1,N, i+1,M);
		Amax = max(Amax, a1+a2);
	}
	printf("%d\n",Amax);
	return 0;
}