Pagini recente » Cod sursa (job #1652312) | Cod sursa (job #2673861) | Cod sursa (job #2831416) | Cod sursa (job #228816) | Cod sursa (job #522297)
Cod sursa(job #522297)
#include <cstdio>
const int N = 205;
int L[N][N], l[N][N], n, m, a[N][N], b[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, l1 ,c1, l2, c2;
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] =='1')
l[i][j] = 0, L[i][j] = 0;
else {
l1 = max(min(L[i][j - 1] + 1, L[i - 1][j]), 1);
c1 = l[i - 1][j] + 1;
l2 = L[i][j - 1] + 1;
c2 = max(1, min(l[i][j - 1], l[i - 1][j] + 1));
if(l1 * c1 > l2 * c2)
L[i][j] = l1, l[i][j] = c1;
else
L[i][j] = l2, l[i][j] = c2;
}
a[i][j] = max(a[i][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 {
l1 = max(min(L[i][j + 1] + 1, L[i + 1][j]), 1);
c1 = l[i + 1][j] + 1;
l2 = L[i][j + 1] + 1;
c2 = max(1, min(l[i][j -1], l[i - 1][j] + 1));
if(l1 * c1 > l2 * c2)
L[i][j] = l1, l[i][j] = c1;
else
L[i][j] = l2, l[i][j] = c2;
}
b[i][j] = max(b[i][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];
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;
}