Pagini recente » Cod sursa (job #812435) | Cod sursa (job #2302809) | Cod sursa (job #2741103) | Cod sursa (job #2297073) | Cod sursa (job #2711262)
#include <fstream>
#include <stack>
using namespace std;
ifstream fin( "bmatrix.in" );
ofstream fout( "bmatrix.out" );
const int Lim = 202;
int M[Lim][Lim];
int d[Lim][Lim];
int l[Lim], r[Lim];
stack<int> s;
int x1, _y1, x2, y2, line;
inline void getLR() {
for ( int i = _y1; i <= y2; ++i ) {
l[i] = _y1 - 1;
r[i] = 0;
}
for ( int i = _y1; i <= y2; ++i ) {
while ( s.size() && d[line][s.top()] > d[line][i] ) {
r[s.top()] = i;
s.pop();
}
s.push( i );
}
while ( s.size() ) s.pop();
for ( int i = y2; i >= _y1; --i ) {
while ( s.size() && d[line][s.top()] > d[line][i] ) {
l[s.top()] = i;
s.pop();
}
s.push( i );
}
while ( s.size() ) s.pop();
for ( int i = _y1; i <= y2; ++i ) {
if ( !r[i] ) {
r[i] = y2 + 1;
}
}
}
inline int MaxArea() {
for ( int i = x1; i <= x2; ++i ) {
for ( int j = _y1; j <= y2; ++j ) {
if ( M[i][j] == 0 ) {
if ( i != x1 ) {
d[i][j] = d[i - 1][j] + 1;
} else {
d[i][j] = 1;
}
}
}
}
int maxa = 0;
for ( int i = x1; i <= x2; ++i ) {
line = i;
getLR();
for ( int j = _y1; j <= y2; ++j ) {
if ( (r[j] - l[j] - 1) * d[i][j] > maxa ) {
maxa = (r[j] - l[j] - 1) * d[i][j];
}
}
}
return maxa;
}
char str[Lim];
int main() {
int n, m, mx, res1, res2;
fin >> n >> m;
for ( int i = 1; i <= n; ++i ) {
fin >> str;
for ( int j = 1; j <= m; ++j ) {
M[i][j] = str[j - 1] - '0';
}
}
mx = 0;
for ( int i = 1; i < n; ++i ) {
x1 = 1, x2 = i, _y1 = 1, y2 = m;
res1 = MaxArea();
x1 = i + 1, x2 = n, _y1 = 1, y2 = m;
res2 = MaxArea();
mx = mx < (res1 + res2) ? (res1 + res2) : mx;
}
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= m; ++j ) {
d[i][j] = l[j] = r[j] = 0;
}
}
for ( int j = 1; j < m; ++j ) {
x1 = 1, x2 = n, _y1 = 1, y2 = j;
res1 = MaxArea();
x1 = 1, x2 = n, _y1 = j + 1, y2 = m;
res2 = MaxArea();
mx = mx < (res1 + res2) ? (res1 + res2) : mx;
}
fout << mx;
fin.close();
fout.close();
return 0;
}