Pagini recente » Cod sursa (job #2208998) | Cod sursa (job #2179452) | Cod sursa (job #3142699) | Cod sursa (job #333755)
Cod sursa(job #333755)
#include <stdio.h>
#define DIM 205
int a[DIM][DIM],s1[DIM][DIM],s2[DIM][DIM],f1[DIM][DIM],f2[DIM][DIM];
int n,m,rez;
void read ()
{
char buff[DIM];
int i,j;
scanf ("%d%d\n",&n,&m);
for (i=1; i<=n; ++i)
{
gets (buff);
for (j=1; j<=m; ++j)
a[i][j]=buff[j-1]-'0';
}
}
void proc ()
{
int i,j,k,min;
for (i=1; i<=n; ++i)
for (j=1; j<=m; ++j)
{
if (!a[i][j])
{
min=f1[i][j]=s1[i][j]=s1[i][j-1]+1;
for (k=i-1; k>=1 && s1[k][j]; --k)
{
if (s1[k][j]<min)
min=s1[k][j];
if (min*(i-k+1)>f1[i][j])
f1[i][j]=min*(i-k+1);
}
}
if (f1[i-1][j]>f1[i][j])
f1[i][j]=f1[i-1][j];
if (f1[i][j-1]>f1[i][j])
f1[i][j]=f1[i][j-1];
}
for (i=n; i>=1; --i)
for (j=m; j>=1; --j)
{
if (!a[i][j])
{
min=f2[i][j]=s2[i][j]=s2[i][j+1]+1;
for (k=i+1; k<=n && s2[k][j]; ++k)
{
if (s2[k][j]<min)
min=s2[k][j];
if (min*(k-i+1)>f2[i][j])
f2[i][j]=min*(k-i+1);
}
}
if (f2[i+1][j]>f2[i][j])
f2[i][j]=f2[i+1][j];
if (f2[i][j+1]>f2[i][j])
f2[i][j]=f2[i][j+1];
}
}
void solve ()
{
int i;
for (i=1; i<=n; ++i)
if (f1[i][m]+f2[i+1][1]>rez)
rez=f1[i][m]+f2[i+1][1];
for (i=1; i<=m; ++i)
if (f1[n][i]+f2[1][i+1]>rez)
rez=f1[n][i]+f2[1][i+1];
printf ("%d",rez);
}
int main ()
{
freopen ("bmatrix.in","r",stdin);
freopen ("bmatrix.out","w",stdout);
read ();
proc ();
solve ();
return 0;
}