Pagini recente » Cod sursa (job #2931082) | Cod sursa (job #517265) | Cod sursa (job #2863141) | Cod sursa (job #884106) | Cod sursa (job #798399)
Cod sursa(job #798399)
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct bmatrix {
int x, y;
bmatrix() {
x = y = 0;
}
bmatrix(int x, int y) {
this->x = x;
this->y = y;
}
};
const int N = 205;
int n, m, head;
int a[N][N];
int up[N], left[N], up2[N], left2[N];
bmatrix stack[N];
char mat[N][N], mat2[N][N];
void read() {
assert(freopen("bmatrix.in", "r", stdin) != NULL);
assert(freopen("bmatrix.out", "w", stdout) != NULL);
assert(scanf("%d %d", &n, &m) == 2);
for (int i = 1; i <= n; ++i)
assert(scanf("%s", mat[i] + 1) == 1);
}
void zero() {
memset(a, 0, sizeof(a));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (mat[i - 1][j] == '0')
a[i][j] = a[i - 1][j] + 1;
else
a[i][j] = 0;
}
}
int dr(int x) {
int maxSol = 0, left;
stack[head = 1] = bmatrix(a[x][1], 1);
for (int i = 2; i <= m; ++i) {
left = i;
while (head > 0 && stack[head].x >= a[x][i]) {
left = stack[head].y;
maxSol = max(maxSol, (i - stack[head].y) * stack[head].x);
--head;
}
stack[++head] = bmatrix(a[x][i], left);
}
while (head > 0) {
maxSol = max(maxSol, (m + 1 - stack[head].y) * stack[head].x);
--head;
}
return maxSol;
}
void preproc(int v[]) {
for (int i = 0; i <= n + 1; ++i)
v[i] = 0;
for (int i = 1; i <= n + 1; ++i)
v[i] = max(v[i - 1], dr(i));
}
void rotate() {
memset(mat2, 0, sizeof(mat2));
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
mat2[i][j] = mat[n - j + 1][i];
//memcpy(mat, mat2, sizeof(mat2));
memset(mat, 0, sizeof(mat));
swap(n, m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
mat[i][j] = mat2[i][j];
/*for (int i = 1; i <= n; ++i, printf("\n"))
for (int j = 1; j <= m; ++j)
printf("%c", mat[i][j]);*/
}
int main() {
read();
zero();
preproc(up);
/*for (int i = 1; i <= n + 1; ++i)
printf("%d ", up[i]);
printf("\n");*/
rotate();
zero();
preproc(left);
/*for (int i = 1; i <= n + 1; ++i)
printf("%d ", left[i]);
printf("\n");*/
rotate();
zero();
preproc(up2);
/*for (int i = 1; i <= n + 1; ++i)
printf("%d ", up2[i]);
printf("\n");*/
rotate();
zero();
preproc(left2);
/*for (int i = 1; i <= n + 1; ++i)
printf("%d ", left2[i]);*/
int sol = 0;
for (int i = 1; i <= n + 1; ++i)
if (up[i] > 0 && up2[n - i + 1] > 0)
sol = max(sol, up[i] + up2[n - i + 1]);
//printf("%d\n", sol);
for (int i = 1; i <= n + 1; ++i)
if (left[i] > 0 && left2[i] > 0)
sol = max(sol, left[i] + left2[n - i + 1]);
printf("%d\n", sol);
}