Pagini recente » Cod sursa (job #2514021) | Cod sursa (job #1414797) | Cod sursa (job #1496318) | Cod sursa (job #1978933) | Cod sursa (job #938647)
Cod sursa(job #938647)
#include <fstream>
using namespace std;
int N, M;
char a[211];
int mat[211][211];
int mataux[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');
mataux[i][j + 1] = mat[i][j + 1];
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) * mataux[i][j];
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) - max (Y, stanga[i][j]) - 1) * mat[i][j] * mataux[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;
}