Pagini recente » Cod sursa (job #2847899) | Cod sursa (job #2413)
Cod sursa(job #2413)
# include <stdio.h>
# include <string.h>
# define maxn 202
# 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;
}