Pagini recente » Cod sursa (job #3236381) | Cod sursa (job #382365) | Cod sursa (job #554361) | Cod sursa (job #1678217) | Cod sursa (job #938649)
Cod sursa(job #938649)
#include <fstream>
using namespace std;
int N, M;
char a[211];
int mat[211][211];
int stanga[211][211];
int dreapta[211][211];
int stiva[211];
void Citire ()
{
ifstream fin ("bmatrix.in");
fin >> N >> M;
for (int i = 1; i <= N; i++)
{
fin >> a;
for (int j = 0; j < M; j++)
{
mat[i][j + 1] = !(a[j] - '0');
if (mat[i][j + 1]) mat[i][j + 1] += mat[i - 1][j + 1];
}
}
fin.close ();
}
void Precalc ()
{
for (int i = 1, cnt; i <= N; i++)
{
stiva[0] = 0;
cnt = 0;
for (int j = 1; j <= M; j++)
{
while (cnt && mat[i][stiva[cnt]] >= mat[i][j]) cnt--;
stanga[i][j] = stiva[cnt];
stiva[++cnt] = j;
}
cnt = 0;
stiva[0] = M + 1;
for (int j = M; j >= 1; j--)
{
while (cnt && mat[i][stiva[cnt]] >= mat[i][j]) cnt--;
dreapta[i][j] = stiva[cnt];
stiva[++cnt] = j;
}
}
}
int Find_Rect1 (int X, int N)
{
int Ans = 0, a;
for (int i = X; i <= N; i++)
for (int j = 1; j <= M; j++)
{
a = dreapta[i][j] - stanga[i][j] - 1;
a *= min (mat[i][j], i - X + 1);
if (Ans < a) Ans = a;
}
return Ans;
}
int Find_Rect2 (int Y, int M)
{
int Ans = 0, a;
for (int i = 1; i <= N; i++)
for (int j = Y; j <= M; j++)
{
a = (min (dreapta[i][j], M + 1) - max (Y - 1, stanga[i][j]) - 1) * mat[i][j];
if (Ans < a) Ans = a;
}
return Ans;
}
void Scriere ()
{
ofstream fout ("bmatrix.out");
int Ans = 0;
for (int i = 2; i <= N; i++)
{
int a = Find_Rect1 (1, i - 1) + Find_Rect1 (i, N);
if (a > Ans) Ans = a;
}
for (int j = 2; j <= M; j++)
{
int a = Find_Rect2 (1, j - 1) + Find_Rect2 (j, M);
if (a > Ans) Ans = a;
}
fout << Ans;
fout.close ();
}
int main ()
{
Citire ();
Precalc ();
Scriere ();
return 0;
}