Pagini recente » Cod sursa (job #803284) | Cod sursa (job #1807608) | Cod sursa (job #909148) | Cod sursa (job #3226809) | Cod sursa (job #1643120)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int MAX = 210;
int a[MAX][MAX];
int D[MAX][MAX];
int t[MAX][MAX];
int unu[MAX][MAX];
int N, M;
char c;
int maxim;
int x1, y1, x2, y2;
int A, A2;
int main()
{
int i, j, i2, jp, j2;
fin >> N >> M;
for ( i = 1; i <= N; i++ )
for ( j = 1; j <= M; j++ )
{
fin >> c;
a[i][j] = c - '0';
if ( a[i][j] ) D[i][j] = 1, t[i][j] = i, unu[i][j] = i;
else unu[i][j] = unu[i - 1][j];
}
for ( i = 1; i <= N; i++ )
for ( i2 = i + 1; i2 <= N; i2++ )
for ( j = jp = 1; j <= M; j++ )
{
if ( unu[i2][j] >= i )
{
jp = j + 1;
}
else
if ( ( j - jp + 1 ) * ( i2 - i + 1 ) > D[i2][j] )
D[i2][j] = ( j - jp + 1 ) * ( i2 - i + 1 ), t[i2][j] = i;
}
for ( i = 1; i <= N; i++ )
for ( j = 1; j <= M; j++ )
if ( D[i][j] > maxim )
{
if ( i == 5 && j == 6 )
fout << "DA";
maxim = D[i][j];
x2 = i, y2 = j;
x1 = t[i][j];
y1 = j - ( D[i][j] / ( x2 - x1 + 1 ) );
for ( i2 = x2; i2 >= x1; i2-- )
A2 = max( A2, D[i2][y1] + D[i][j] );
for ( j2 = y2; j2 >= y1; j2-- )
A2 = max( A2, D[x1][j2] + D[i][j] );
}
A = maxim;
for ( i = x1; i <= x2; i++ )
for ( j = y1; j <= y2; j++ )
a[i][j] = 1;
memset( D, 0, sizeof(D) );
for ( i = 1; i <= N; i++ )
for ( j = 1; j <= M; j++ )
if ( a[i][j] ) unu[i][j] = i;
else unu[i][j] = unu[i - 1][j];
for ( i = 1; i <= N; i++ )
for ( i2 = i + 1; i2 <= N; i2++ )
for ( j = jp = 1; j <= M; j++ )
{
if ( unu[i2][j] >= i )
{
jp = j + 1;
}
else
if ( ( j - jp + 1 ) * ( i2 - i + 1 ) > D[i2][j] )
D[i2][j] = ( j - jp + 1 ) * ( i2 - i + 1 ), t[i2][j] = i;
}
maxim = 0;
for ( i = 1; i <= N; i++ )
for ( j = 1; j <= M; j++ )
maxim = max( maxim, D[i][j] );
fout << max(A + maxim, A2) << '\n';
fin.close();
fout.close();
return 0;
}