Pagini recente » Cod sursa (job #207132) | Cod sursa (job #1607446) | Cod sursa (job #1183140) | Cod sursa (job #1607439) | Cod sursa (job #496954)
Cod sursa(job #496954)
#include<cstdio>
const int N=1<<8;
int n,m,a[N][N],st[N][N],su[N][N],dsu[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()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]==0)
{
st[i][j]=st[i][j-1]+1;
su[i][j]=su[i-1][j]+1;
}
}
int min(int x,int y)
{
return (x<y && x)?x:y;
}
int getmat(int ax,int ay,int bx,int by)
{
int max=-1;
for(int j=ay;j<=by;j++)
if(a[1][j]==0)
{
dsu[1][j]=1;
dst[1][j]=min(st[1][j],j-ay+1);
}
for(int i=ax;i<=bx;i++)
if(a[i][1]==0)
{
dsu[i][1]=min(su[i][1],i-ax+1);
dst[i][1]=1;
}
for(int i=ax+1;i<=bx;i++)
for(int j=ay+1;j<=by;j++)
if(a[i][j]==0)
{
dsu[i][j]=min(dsu[i-1][j-1]+1,min(su[i][j],i-ax+1));
dst[i][j]=min(dst[i-1][j-1]+1,min(st[i][j],j-ay+1));
if(dsu[i][j]*dst[i][j]>max)
max=dsu[i][j]*dst[i][j];
}
return max;
}
void resetl(int x)
{
for(int j=1;j<=m;j++)
dsu[x][j]=dst[x][j]=0;
}
void resetc(int y)
{
for(int i=1;i<=n;i++)
dsu[i][y]=dst[i][y]=0;
}
void solve()
{
int max=-1,x,y;
for(int i=2;i<=n;i++)
{
x=getmat(1,1,i-1,m);
resetl(i-1);
y=getmat(i,1,n,m);
if(x+y>max)
max=x+y;
}
for(int j=2;j<=m;j++)
{
x=getmat(1,1,n,j-1);
resetc(j-1);
y=getmat(1,j,n,m);
if(x+y>max)
max=x+y;
}
printf("%d",max);
}
void afis(int a[N][N])
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
printf("%d",a[i][j]);
printf("\n");
}
}
int main()
{
read();
init();
solve();
return 0;
}