Pagini recente » Cod sursa (job #1054839) | Cod sursa (job #2208290) | Cod sursa (job #2974344) | Cod sursa (job #1542282) | Cod sursa (job #70967)
Cod sursa(job #70967)
#include <stdio.h>
#include <memory.h>
#define NMAX 205
int a[NMAX][NMAX];
int b[NMAX][NMAX];
int cache[NMAX];
int n, m;
int max;
//#define cache (cache-1)
void read()
{
int i, j;
char c[NMAX];
scanf("%d%d\n", &n, &m);
for(i = 1; i <= n; ++i)
{
scanf("%s", c+1);
for(j = 1; j <= m; ++j)
{
//scanf("%c", &c);
if(c[j] == '0')
a[i][j] = 0;
else
a[i][j] = 1;
}
}
}
int compute(int count)
{
int stackHeight[NMAX];
int stackPos[NMAX];
int size = 0;
cache[++count] = 0;
/* for (int j = 0; j < count; ++j) {
cout << cache[j] << " ";
}
cout << endl;*/
memset(stackHeight, 0, sizeof(stackHeight));
memset(stackPos, 0, sizeof(stackPos));
stackHeight[0] = 0;
stackPos[0] = -1;
size = 1;
int result = 0;
for (int j = 0; j <= count; ++j) {
int cpos = j;
while (size > 0 && stackHeight[size - 1] >= cache[j]) {
cpos = stackPos[size - 1];
int h = stackHeight[size - 1];
int w = j - stackPos[size - 1];
if (h * w > result) {
result = h * w;
}
size--;
}
if (cache[j] > stackHeight[size - 1]) {
stackHeight[size] = cache[j];
stackPos[size] = cpos;
size++;
}
}
return result;
}
void solve()
{
int i, j;
int above[NMAX], below[NMAX];
memset(above, 0, sizeof(above));
memset(below, 0, sizeof(below));
memset(cache, 0, sizeof(cache));
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= m; ++j)
if(a[i][j])
cache[j] = 0;
else
++cache[j];
below[i] = compute(m);
if(below[i-1] > below[i])
below[i] = below[i-1];
}
memset(cache, 0, sizeof(cache));
for(i = n; i; --i)
{
for(j = 1; j <= m; ++j)
if(a[i][j])
cache[j] = 0;
else
++cache[j];
above[i] = compute(m);
if(above[i+1] > above[i])
above[i] = above[i+1];
}
for(i = 0; i <= n; ++i)
if(below[i] + above[i+1] > max)
max = below[i] + above[i+1];
}
void invert()
{
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
b[j][i] = a[i][j];
memcpy(a, b, sizeof(b));
int aux = n;
n = m;
m = aux;
}
void print()
{
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
printf("%d", a[i][j]);
printf("\n");
}
printf("%d %d\n", n, m);
}
int main()
{
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
read();
solve();
invert();
//print();
solve();
printf("%d\n", max);
return 0;
}