Pagini recente » Cod sursa (job #1187473) | Cod sursa (job #1756842) | Cod sursa (job #2144264) | Cod sursa (job #1101927) | Cod sursa (job #1790295)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MaxN 205
#define INF 65000
FILE *IN,*OUT;
unsigned short N,M,L[MaxN][MaxN],C[MaxN][MaxN],RL[MaxN][MaxN],RC[MaxN][MaxN];
struct coord{unsigned short x,y,Size;}Fwd[MaxN][MaxN],Rect[MaxN][MaxN],Bkd[MaxN][MaxN];
bool v[MaxN][MaxN];
char Ch;
inline unsigned short min(unsigned short a,unsigned short b)
{
if(a<b)
return a;
else return b;
}
inline unsigned short max(unsigned short a,unsigned short b)
{
if(a>b)
return a;
else return b;
}
int main()
{
IN=fopen("bmatrix.in","r");
OUT=fopen("bmatrix.out","w");
fscanf(IN,"%d%d ",&N,&M);
for(unsigned short i=1;i<=N;i++)
for(unsigned short j=1;j<=M;j++)
{
fscanf(IN,"%c ",&Ch);
v[i][j]=Ch-'0';
}
for(unsigned short i=1;i<=N;i++)
for(unsigned short j=1;j<=M;j++)
{
if(v[i][j])
L[i][j]=C[i][j]=0;
else
{
L[i][j]=L[i][j-1]+1;
C[i][j]=C[i-1][j]+1;
}
}
for(unsigned short i=N;i>0;i--)
for(unsigned short j=M;j>0;j--)
{
if(v[i][j])
RL[i][j]=RC[i][j]=0;
else
{
RL[i][j]=RL[i][j+1]+1;
RC[i][j]=RC[i+1][j]+1;
}
}
for(unsigned short i=1;i<=N;i++)
for(unsigned short j=1;j<=M;j++)
{
if(v[i][j])
{
Fwd[i][j].x=i,Fwd[i][j].y=j,Fwd[i][j].Size=0;
Rect[i][j]=Fwd[i][j];
}
else
{
unsigned short Max=INF;
for(unsigned short k=i;k>=i-C[i][j]+1;k--)
{
Max=min(Max,L[k][j]);
if(Fwd[i][j].Size<Max*(i-k+1))
{
Fwd[i][j].x=k;
Fwd[i][j].y=j-Max+1;
Fwd[i][j].Size=(i-k+1)*Max;
Rect[i][j]=Fwd[i][j];
}
}
}
if(Fwd[i][j-1].Size>Fwd[i][j].Size)
Fwd[i][j]=Fwd[i][j-1];
if(Fwd[i-1][j].Size>Fwd[i][j].Size)
Fwd[i][j]=Fwd[i-1][j];
}
for(unsigned short i=N;i>0;i--)
for(unsigned short j=M;j>0;j--)
{
if(v[i][j])
Bkd[i][j].x=i,Bkd[i][j].y=j,Bkd[i][j].Size=0;
else
{
int Max=INF;
for(unsigned short k=i;k<=i+RC[i][j]-1;k++)
{
Max=min(Max,RL[k][j]);
if(Bkd[i][j].Size<(k-i+1)*Max)
{
Bkd[i][j].x=k;
Bkd[i][j].y=j+Max-1;
Bkd[i][j].Size=(k-i+1)*Max;
}
}
}
if(Bkd[i][j+1].Size>Bkd[i][j].Size)
Bkd[i][j]=Bkd[i][j+1];
if(Bkd[i+1][j].Size>Bkd[i][j].Size)
Bkd[i][j]=Bkd[i+1][j];
}
unsigned short Total=0;
for(unsigned short i=1;i<=N;i++)
for(unsigned short j=1;j<=M;j++)
{
Total=max(Total,Rect[i][j].Size+(max(max(Fwd[N][Rect[i][j].y-1].Size,Fwd[Rect[i][j].x-1][M].Size),max(Bkd[i+1][1].Size,Bkd[1][j+1].Size))));
}
fprintf(OUT,"%d",Total);
return 0;
}