Pagini recente » Cod sursa (job #2634290) | Cod sursa (job #1055343) | Cod sursa (job #2363616) | Cod sursa (job #2891107) | Cod sursa (job #3276669)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int n, m, a[205][205], sp[205][205], sol, c[205], c2[205];
int st[205], top, stg[205], drp[205];
int st2[205], top2, stg2[205], drp2[205];
char ch[205];
pair<int, int> ss, dj;
void Verifica(int maxi)
{
int i, j, maxim = 0, x, arie;
for(i = ss.first;i <= dj.first;i++)
for(j = ss.second;j <= dj.second;j++)
a[i][j] = 1;
for(j = 1;j <= m;j++)
c2[j] = 0;
for(i = 1;i <= n;i++)
{
for(j = 1;j <= m;j++)
if(a[i][j] == 0) c2[j]++;
else c2[j] = 0;
top2 = 0;st2[0] = 0;
for(j = 1;j <= m;j++)
{
x = c2[j];
while(top2 > 0 && c2[j] <= c2[st2[top2]])
top2--;
stg2[j] = st2[top2];
st2[++top2] = j;
}
top2 = 0;st2[0] = m + 1;
for(j = m;j >= 1;j--)
{
x = c2[j];
while(top2 > 0 && c2[j] <= c2[st2[top2]])
top2--;
drp2[j] = st2[top2];
st2[++top2] = j;
}
for(j = 1;j <= m;j++)
{
arie = c2[j] * (drp2[j] - stg2[j] - 1);
if(arie > maxim)
maxim = arie;
}
}
sol = max(sol, maxi + maxim);
for(i = ss.first;i <= dj.first;i++)
for(j = ss.second;j <= dj.second;j++)
a[i][j] = 0;
}
int main()
{
int i, j, x, l1, l2, maxi, arie;
fin >> n >> m;
fin.get();
for(i = 1;i <= n;i++)
{
fin >> ch;
for(j = 1;j <= m;j++)
a[i][j] = ch[j - 1] - '0';
}
for(i = 1;i <= n;i++)
{
maxi = 0;
for(j = 1;j <= m;j++)
if(a[i][j] == 0) c[j]++;
else c[j] = 0;
top = 0;
for(j = 1;j <= m;j++)
{
x = c[j];
while(top > 0 && c[j] <= c[st[top]])
top--;
stg[j] = st[top];
st[++top] = j;
}
top = 0;st[0] = m + 1;
for(j = m;j >= 1;j--)
{
x = c[j];
while(top > 0 && c[j] <= c[st[top]])
top--;
drp[j] = st[top];
st[++top] = j;
}
for(j = 1;j <= m;j++)
{
arie = c[j] * (drp[j] - stg[j] - 1);
if(arie > maxi)
{
maxi = arie;
ss = {i - c[j] + 1, stg[j] + 1};
dj = {i, drp[j] - 1};
}
}
Verifica(maxi);
}
fout << sol << "\n";
fout.close();
return 0;
}