Pagini recente » Cod sursa (job #2986614) | Cod sursa (job #192491) | Cod sursa (job #3176856) | Cod sursa (job #1996263) | Cod sursa (job #496972)
Cod sursa(job #496972)
#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[ax][j]==0)
{
dsu[ax][j]=1;
dst[ax][j]=min(st[ax][j],j-ay+1);
if(dsu[ax][j]*dst[ax][j]>max)
max=dsu[ax][j]*dst[ax][j];
}
for(int i=ax;i<=bx;i++)
if(a[i][ay]==0)
{
dsu[i][ay]=min(su[i][ay],i-ax+1);
dst[i][ay]=1;
if(dsu[i][ay]*dst[i][ay]>max)
max=dsu[i][ay]*dst[i][ay];
}
for(int i=ax+1;i<=bx;i++)
for(int j=ay+1;j<=by;j++)
if(a[i][j]==0)
{
if(st[i][j]>1)
dsu[i][j]=min(dsu[i-1][j-1]+1,min(su[i][j],i-ax+1));
else dsu[i][j]=min(su[i][j],i-ax+1);
if(su[i][j]>1)
dst[i][j]=min(dst[i-1][j-1]+1,min(st[i][j],j-ay+1));
else dst[i][j]=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 solve()
{
int max=-1,x,y;
for(int i=2;i<=n;i++)
{
x=getmat(1,1,i-1,m);
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);
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;
}