Pagini recente » Cod sursa (job #1452942) | Cod sursa (job #2942753) | Cod sursa (job #2044543) | Cod sursa (job #1162453) | Cod sursa (job #198740)
Cod sursa(job #198740)
#include <stdio.h>
#define maxn 210
char a[maxn][maxn],b[maxn][maxn];
int n,m,sol;
int o[maxn][maxn],u[maxn][maxn],v[maxn][maxn];
int d1[maxn],d2[maxn],s[maxn],l,p[maxn];
void rotate()
{
int i,j,aux;
for (i=0;i<m;i++)
for (j=0;j<n;j++)
b[i][j]=a[n-j-1][i];
aux=n;
n=m;
m=aux;
for (i=0;i<n;i++)
for (j=0;j<m;j++) a[i][j]=b[i][j];
}
void symetric()
{
int i,j,aux;
for (i=0;i<n;i++)
for (j=0;j<m/2;j++)
{
aux=a[i][j];
a[i][j]=a[i][m-j-1];
a[i][m-j-1]=aux;
}
}
void solve()
{
int i,j,aux;
for (i=0;i<m;i++) d1[i]=0;
for (i=0;i<n;i++)
if (a[i][0]=='1') o[i][0]=0;
else o[i][0]=1;
for (i=0;i<n;i++)
for (j=1;j<m;j++)
if (a[i][j]=='1') o[i][j]=0;
else o[i][j]=o[i][j-1]+1;
for (j=0;j<m;j++)
{
l=0;
s[l]=0;
for (i=0;i<n;i++)
{
if (o[i][j]>s[l])
{
l++;
s[l]=o[i][j];
p[l]=i;
}
else {
while ((l>0) && (o[i][j]<s[l])) l--;
if (s[l]<o[i][j])
{
l++;
s[l]=o[i][j];
}
}
v[i][j]=i-p[l]+1;
}
}
for (j=0;j<m;j++)
{
l=0;
s[l]=0;
for (i=n-1;i>=0;i--)
{
if (o[i][j]>s[l])
{
l++;
s[l]=o[i][j];
p[l]=i;
}
else {
while ((l>0) && (o[i][j]<s[l])) l--;
if (o[i][j]>s[l])
{
l++;
s[l]=o[i][j];
}
}
u[i][j]=p[l]-i+1;
}
}
for (i=0;i<n;i++)
for (j=0;j<m;j++)
{
aux=(v[i][j]+u[i][j]-1)*o[i][j];
if (aux>d1[j]) d1[j]=aux;
}
for (i=1;i<m;i++)
if (d1[i-1]>d1[i]) d1[i]=d1[i-1];
}
int main()
{
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
scanf("%d %d ",&n,&m);
int i;
for (i=0;i<n;i++)
fgets(a[i],maxn,stdin);
solve();
for (i=0;i<m;i++) d2[i]=d1[i];
symetric();
solve();
for (i=0;i<m;i++)
if (d2[i]+d1[m-i-2]>sol) sol=d2[i]+d1[m-i-2];
rotate();
solve();
for (i=0;i<m;i++) d2[i]=d1[i];
symetric();
solve();
for (i=0;i<m;i++)
if (d2[i]+d1[m-i-2]>sol) sol=d2[i]+d1[m-i-2];
printf("%d\n",sol);
return 0;
}