Pagini recente » Cod sursa (job #2232700) | Cod sursa (job #1196903) | Cod sursa (job #1183110) | Cod sursa (job #599167) | Cod sursa (job #496996)
Cod sursa(job #496996)
#include<cstdio>
const int N=1<<8;
int sol,n,m,g[N],h[N],a[N][N],st[N][N],jo[N][N],djo[N][N],dst[N][N];
void read()
{
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
scanf("%d%d\n",&n,&m);
char s[N];
for(int i=1;i<=n;i++)
{
gets(s);
for(int j=1;j<=m;j++)
a[i][j]=s[j-1]-'0';
}
}
void init()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j]==0)
st[i][j]=st[i][j-1]+1;
for(i=1;i<=n;i++)
for(j=m;j>=1;j--)
if(a[i][j]==0)
jo[i][j]=jo[i][j+1]+1;
}
int min(int x,int y)
{
return x<y?x:y;
}
int max(int x,int y)
{
return x>y?x:y;
}
void getmat1()
{
int x;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
x=st[i][j];
dst[i][j]=x;
for(int k=i-1;k>=1;k--)
{
x=min(x,st[k][j]);
if(!x)
break;
dst[i][j]=max(dst[i][j],(i-k+1)*x);
}
}
}
void getmat2()
{
int y;
for(int i=n;i>=1;i--)
for(int j=1;j<=m;j++)
{
y=jo[i][j];
djo[i][j]=y;
for(int k=i+1;k<=n;k++)
{
y=min(y,jo[k][j]);
if(!y)
break ;
djo[i][j]=max(djo[i][j],(k-i+1)*y);
}
}
}
void solveor()
{
int bs=0;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=m;j++)
bs=max(bs,dst[i-1][j]);
g[i]=bs;
}
bs=0;
for(int i=n-1;i>=1;i--)
{
for(int j=1;j<=m;j++)
bs=max(bs,djo[i+1][j]);
h[i]=bs;
}
for(int i=2;i<=n;i++)
sol=max(sol,g[i]+h[i-1]);
}
void solveve()
{
int bs;
bs=0;
for(int j=2;j<=m;j++)
{
for(int i=1;i<=n;i++)
bs=max(bs,dst[i][j-1]);
g[j]=bs;
}
bs=0;
for(int j=m-1;j>=1;j--)
{
for(int i=1;i<=n;i++)
bs=max(bs,djo[i][j+1]);
h[j]=bs;
}
for(int i=2;i<=m;i++)
sol=max(sol,g[i]+h[i-1]);
}
int main()
{
read();
init();
getmat1();
getmat2();
solveor();
solveve();
printf("%d",sol);
return 0;
}