Pagini recente » Cod sursa (job #2855606) | Cod sursa (job #2181822) | Cod sursa (job #3174875) | Cod sursa (job #2199335) | Cod sursa (job #522310)
Cod sursa(job #522310)
#include <cstdio>
const int N = 205;
int L[N][N], l[N][N], n, m, a[N][N], b[N][N], x[N][N], y[N][N];
char c[N][N];
int min(int a, int b) {
return a < b ? a : b;
}
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
int j, i, c1;
char C;
scanf("%d %d", &n, &m);
for(i = 1;i <= n; ++i) {
scanf("%c", &c);
for(j = 1; j <= m; ++j)
scanf("%c", &c[i][j]);
}
for(i = 1; i <= n; ++i)
for(j = 1; j <= m; ++j)
if(c[i][j] == '0')
x[i][j] = x[i][j - 1] + 1;
else
x[i][j] = 0;
for(i = n; i >= 1; --i)
for(j = m; j >= 1; --j)
if(c[i][j] == '0')
y[i][j] = y[i][j + 1] + 1;
else
y[i][j] = 0;
int k;
for(i = 1; i <= n; ++i)
for(j = 1; j <=m; ++j) {
if(c[i][j] =='1')
l[i][j] = 0, L[i][j] = 0;
else {
L[i][j] = x[i][j];
l[i][j] = 1;
c1 = x[i][j];
for(k = i - 1; k >= 1; --k) {
c1 = min(c1, x[k][j]);
if(L[i][j] * l[i][j] < c1 * (i - k + 1))
L[i][j] = c1, l[i][j] = i - k +1 ;
}
}
a[i][j] = max(a[i][j - 1], max(a[i - 1][j - 1],a[i - 1][j]));
a[i][j] = max(a[i][j], L[i][j] * l[i][j]);
}
for(i = 1; i <= n; ++i)
for(j = 1; j <= m; ++j)
L[i][j] = l[i][j] = 0;
for(i = n; i >= 1; --i)
for(j = m; j >= 1; --j) {
if(c[i][j] =='1')
l[i][j] = 0, L[i][j] = 0;
else {
c1 = y[i][j];
L[i][j] = y[i][j];
l[i][j] = 1;
for(k = i + 1; k <= n; ++k) {
c1 = min(c1, y[k][j]);
if(L[i][j] * l[i][j] < c1 * (k - i +1))
L[i][j] = c1, l[i][j] = k - i + 1;
}
}
b[i][j] = max(b[i][j + 1], max(b[i +1][j + 1], b[i + 1][j]));
b[i][j] = max(L[i][j] * l[i][j], b[i][j]);
}
int s = 0;
for(i = 1; i <= n - 1; ++i)
if(a[i][m] + b[i + 1][1] > s)
s = a[i][m] + b[i +1][1];
for(i = 1; i <= m- 1; ++i)
if(a[n][i] + b[1][i + 1] > s)
s = a[n][i] + b[1][i + 1];
printf("%d \n", s);/*
for(i = 1; i <= n; ++i) {
for(j = 1; j <= m; ++j)
printf("%d ", b[i][j] );
printf("\n");
}
*/
return 0;
}