Cod sursa(job #2694)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 18 decembrie 2006 17:38:52
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
# include <stdio.h>
# include <string.h>

# define  maxn  220

# define  _fin  "bmatrix.in"
# define  _fout "bmatrix.out"


int n, m;
int v[maxn], a[maxn][maxn];
int s[maxn], sol;


void readf()
{
	FILE *fin = fopen(_fin, "r");
	int i, j;
	char row[maxn];
	
	for (fscanf(fin, "%d %d\n", &n, &m), i=1; i<=n; i++)
	{
		fgets(row, maxn, fin);
		for (j=0; j<m; j++)
			a[i][j+1] = row[j] - '0';
	}
	
	fclose(fin);
}

int submatrix(int left, int top, int right, int down)
{
	int i, j, cols, aux, best=0, crt;
	memset(v, 0, sizeof(v));
	
	for (i=top; i<=down; i++)
	{
		for (s[0]=0, j=left; j<=right; j++)
		{
			if ( !a[i][j] ) ++v[j];
			else v[j] = 0;
			
			if ( !v[j] )
			{
				// scotem toate din lista
				cols=1;
				while ( s[0] )
				{
					if ( (aux = s[ s[0] ] * cols) > best ) best = aux;
					--s[0], ++cols;
				}
			}
			
			else if ( v[j] < s[ s[0] ] )
			{
				// le facem pe toate de aceasta dimensiune
				cols=1, crt=s[0];
				while ( v[j] < s[ crt ] && crt )
				{
					if ( (aux = s[ crt ] * cols) > best ) best = aux;
					s[ crt ] = v[j];
					--crt, ++cols;
				}
			}
			
			s[ ++s[0] ] = v[j];
		}
		
		cols=1;
		while ( s[0]>=1 )
		{
			if ( (aux = s[ s[0] ] * cols ) > best ) best = aux;
			--s[0], ++cols;
		}
	}
		
	return best;
}

void solve()
{
	int i, aux;
	
	for (i=1; i<m; i++)	// impartim matricea printr-o linie verticala
		if ( ( aux = submatrix(1,1,i,n) + submatrix(i+1,1,m,n) ) > sol )
			sol = aux;
	for (i=1; i<n; i++)	// impartim matricea printr-o linie orizontala
		if ( ( aux = submatrix(1,1,m,i) + submatrix(1,i+1,m,n) ) > sol )
			sol = aux;
}

void writef()
{
	FILE *fout = fopen(_fout, "w");
	fprintf(fout, "%d\n", sol), fclose(fout);
}

int main()
{
	readf();
	solve();
	writef();
	
	return 0;
}