Pagini recente » Cod sursa (job #843168) | Cod sursa (job #1561260) | Cod sursa (job #2937648) | Cod sursa (job #1887693) | Cod sursa (job #673839)
Cod sursa(job #673839)
#include <cstdio>
#include <stack>
#define NMAX 200
using namespace std;
int aux[NMAX][NMAX], a[NMAX][NMAX],m , n;
int best_dr(int x1, int y1, int x2, int y2) //stanga sus, dreapta jos
{
for(int i=x1;i<=x2;++i)
{
aux[y1-1][i] = 0;
}
for(int i=y1;i<=y2;++i)
{
for(int j=x1;j<=x2;++j)
{
if(a[i][j] == 0)
{
aux[i][j] = aux[i-1][j] + 1;
}
else
{
aux[i][j] = 0;
}
}
}
int best = 0;
for(int i=y1;i<=y2;++i)
{
stack<pair<int, int> >S;
S.push(make_pair(x1-1,-1));
for(int j=x1;j<=x2;++j)
{
while(aux[i][j] <= S.top().second)
{
S.pop();
}
if(best < aux[i][j] * (j - S.top().first))
{
best = aux[i][j] * (j - S.top().first);
}
S.push(make_pair(j, aux[i][j]));
}
stack<pair<int, int> >S2;
S2.push(make_pair(x2+1,-1));
for(int j=x2;j>=x1;--j)
{
while(aux[i][j] <= S2.top().second)
{
S2.pop();
}
if(best < aux[i][j] * (S2.top().first - j))
{
best = aux[i][j] * (S2.top().first - j);
}
S2.push(make_pair(j, aux[i][j]));
}
}
return best;
}
int main()
{
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
scanf("%d %d", &m, &n);
for(int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j)
{
scanf(" %c ", &a[i][j]);
a[i][j] -= '0';
}
}
int best = 0, b;
for(int i=1;i<n;++i)
{
b = best_dr(1,1,i,m);
b += best_dr(i+1,1,n,m);
if(b > best)
{
best = b;
}
}
for(int i=1;i<m;++i)
{
b = best_dr(1,1,n,i);
b += best_dr(1,i+1,n,m);
if(b > best)
{
best = b;
}
}
printf("%d", best);
return 0;
}