Pagini recente » Cod sursa (job #2522879) | Cod sursa (job #1873269) | Cod sursa (job #10483) | Cod sursa (job #1133219) | Cod sursa (job #17927)
Cod sursa(job #17927)
#include <stdio.h>
#include <string.h>
#define MAXN 205
int N, M;
unsigned char x[MAXN][MAXN], up[MAXN][MAXN];
int best1[MAXN], best2[MAXN];
inline void rotate()
{
int i, j, aux;
for (i = 0; i < N; i++)
for (j = i + 1; j < M; j++)
{
aux = x[i][j];
x[i][j] = x[j][i];
x[j][i] = aux;
}
aux = N;
N = M;
M = aux;
}
inline void horizontalflip()
{
int i, l, r, aux;
for (i = 0; i < M; i++)
for (l = 0, r = N - 1; l < r; l++, r--)
{
aux = x[l][i];
x[l][i] = x[r][i];
x[r][i] = aux;
}
}
void calculatebest( int best[MAXN] )
{
memset(best, 0, sizeof(best));
int i, j, k;
for (i = 0; i < M; i++)
up[0][i] = !x[0][i];
for (i = 1; i < N; i++)
for (j = 0; j < M; j++)
{
if (x[i][j] == 1)
up[i][j] = 0;
else
up[i][j] = up[i - 1][j] + 1;
}
for (i = 0; i < N; i++)
{
int MAX = -0x3f3f3f3f;
for (j = 0; j < M; j++)
{
int MIN = 0x3f3f3f3f;
for (k = j; k < M && MIN; k++)
{
if (up[i][k] < MIN)
MIN = up[i][k];
if (MIN * (k - j + 1) > MAX)
MAX = MIN * (k - j + 1);
}
}
best[i] = MAX;
if (i && best[i - 1] > best[i])
best[i] = best[i - 1];
}
}
inline int getbest()
{
calculatebest( best1 );
if (N == 1)
return best1[0];
horizontalflip();
calculatebest( best2 );
horizontalflip();
int l, r, BEST = -0x3f3f3f3f;
for (l = 0, r = N - 1; l < r; l++, r--)
{
int aux = best2[l];
best2[r] = best2[l];
best2[l] = aux;
}
BEST = best2[0];
for (l = 0; l < N - 1; l++)
if (best1[l] + best2[l + 1] > BEST)
BEST = best1[l] + best2[l + 1];
if (best1[N - 1] > BEST)
BEST = best1[N - 1];
return BEST;
}
int main()
{
freopen("bmatrix.in", "rt", stdin);
freopen("bmatrix.out", "wt", stdout);
scanf("%d %d", &N, &M);
int i, j;
for (i = 0; i < N; i++)
for (j = 0; j < M; j++)
{
scanf(" %c ", x[i] + j);
x[i][j] -= '0';
}
int NR1, NR2;
NR1 = getbest();
rotate();
NR2 = getbest();
printf("%d\n", (NR1 > NR2 ? NR1 : NR2));
return 0;
}