Pagini recente » Cod sursa (job #1196119) | Cod sursa (job #3225680) | Cod sursa (job #604145) | Cod sursa (job #1504637)
#include <cstdio>
#define NMAX 225
int a[NMAX],b[NMAX],c[NMAX];
int mat[NMAX][NMAX],sum[NMAX][NMAX],sum2[NMAX][NMAX];
int n,m;
int max(int a,int b)
{
if(a<b) return b;
return a;
}
int main()
{
freopen ("bmatrix.in","r",stdin);
freopen ("bmatrix.out","w",stdout);
scanf("%d%d",&m,&n);
char ch;
for(int i=1;i<=m;i++)
{
scanf("%c",&ch);
for(int j=1;j<=n;j++)
{
scanf("%c",&ch);
mat[i][j]=ch-'0';
}
}
/* for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
sum[j][i]=sum[j-1][i]+mat[j][i];
}
}*/
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++) sum2[i][j]=sum2[i][j-1]+mat[i][j];
}
/*for(int i=1;i<=m;i++)
{
for(int j=i+1;j<=m;j++)
{
int dist=0;
for(int k=1;k<=n;k++)
{
if(sum[j][k]-sum[i-1][k]==0) dist+=(j-i+1);
else dist=0;
if(a[k]<dist) a[k]=dist;
}
}
}
b[1]=a[1];
a[1]=0;
for(int i=2;i<=n;i++)
{
b[i]=max(a[i],b[i-1]);
a[i]=0;
}
//for(int i=1;i<=n;i++) printf("%d ",b[i]);
//printf("\n");
for(int i=1;i<=m;i++)
{
for(int j=i+1;j<=m;j++)
{
int dist=0;
for(int k=n;k>=1;k--)
{
if(sum[j][k]-sum[i-1][k]==0) dist+=(j-i+1);
else dist=0;
if(a[k]<dist) a[k]=dist;
}
}
}
c[n]=a[n];
for(int i=n-1;i>=1;i--) c[i]=max(a[i],c[i+1]);
*/// for(int i=1;i<=n;i++) printf("%d ",c[i]);
//printf("\n");
int maxim=0;
/*for(int i=1;i<n;i++) maxim=max(maxim,b[i]+c[i+1]);
for(int i=1;i<=n;i++)
{
a[i]=0;
b[i]=0;
c[i]=0;
}*/
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int dist=0;
for(int k=1;k<=m;k++)
{
if(sum2[k][j]-sum2[k][i-1]==0) dist+=(j-i+1);
else dist=0;
if(a[k]<dist) a[k]=dist;
}
}
}
b[1]=a[1];
for(int i=2;i<=m;i++) b[i]=max(b[i-1],a[i]);
for(int i=1;i<=m;i++) a[i]=0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int dist=0;
for(int k=m;k>=1;k--)
{
if(sum2[k][j]-sum2[k][i-1]==0) dist+=(j-i+1);
else dist=0;
if(a[k]<dist) a[k]=dist;
}
}
}
c[m]=a[m];
for(int i=m-1;i>=1;i--) c[i]=max(c[i+1],a[i]);
for(int i=1;i<m;i++) maxim=max(maxim,b[i]+c[i+1]);
//for(int i=1;i<=m;i++) printf("%d ",b[i]);
//printf("\n");
//for(int i=1;i<=m;i++) printf("%d ",c[i]);
printf("%d\n",maxim);
}