Pagini recente » Cod sursa (job #1195885) | Cod sursa (job #462602)
Cod sursa(job #462602)
#include <stdio.h>
#define NMAX 205
int n,m;
char A[NMAX][NMAX];
int B[NMAX][NMAX],H[NMAX][NMAX],C[NMAX][NMAX],D[NMAX][NMAX],rez;
int E[NMAX],F[NMAX];
void read()
{
scanf("%d%d\n",&n,&m);
int i;
for (i=1; i<=n; i++)
fgets(A[i]+1,NMAX,stdin);
}
void compute1()
{
int i,j;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
if (A[i][j]-'0')
B[i][j]=0;
else
B[i][j]=B[i][j-1]+1;
for (i=1; i<=n; i++)
for (j=m; j>=1; j--)
if (A[i][j]-'0')
H[i][j]=0;
else
H[i][j]=H[i][j+1]+1;
}
inline int min(int x,int y)
{
return x<y ? x : y;
}
inline int max(int x,int y)
{
return x>y ? x : y;
}
void compute2()
{
int i,j,k,act;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
{
act=B[i][j];
C[i][j]=act;
for (k=i-1; k>=1; k--)
{
act=min(act,B[k][j]);
if (!act)
break ;
C[i][j]=max(C[i][j],(i-k+1)*act);
}
}
for (i=n; i>=1; i--)
for (j=1; j<=m; j++)
{
act=H[i][j];
D[i][j]=act;
for (k=i+1; k<=n; k++)
{
act=min(act,H[k][j]);
if (!act)
break ;
D[i][j]=max(D[i][j],(k-i+1)*act);
}
}
}
void solve()
{
int i,j,best=0;
for (i=2; i<=n; i++)
{
for (j=1; j<=m; j++)
best=max(best,C[i-1][j]);
E[i]=best;
}
best=0;
for (i=n-1; i>=1; i--)
{
for (j=1; j<=m; j++)
best=max(best,D[i+1][j]);
F[i]=best;
}
for (i=2; i<=n; i++)//separator orizontala
rez=max(rez,E[i]+F[i-1]);
best=0;
for (j=2; j<=m; j++)
{
for (i=1; i<=n; i++)
best=max(best,C[i][j-1]);
E[j]=best;
}
best=0;
for (j=m-1; j>=1; j--)
{
for (i=1; i<=n; i++)
best=max(best,D[i][j+1]);
F[j]=best;
}
for (i=2; i<=m; i++) //separator verticala
rez=max(rez,E[i]+F[i-1]);
}
int main()
{
freopen("submatrix.in","r",stdin);
freopen("submatrix.out","w",stdout);
read();
compute1();
compute2();
solve();
printf("%d\n",rez);
return 0;
}