Pagini recente » Cod sursa (job #1490849) | Cod sursa (job #1696063) | Cod sursa (job #1861843) | Cod sursa (job #98515) | Cod sursa (job #876133)
Cod sursa(job #876133)
#include<fstream>
#include<cstring>
using namespace std;
int n,m,sol;
char mat[210][210],A[2][210][210];
struct Turn{int h,j;};
Turn a[210],stiva[210];
int vf=-1,Nr[210][210];
inline int ArieMax(int p,int n,int m)
{
int i,arie,ariemax=0,x,k,i1,nr;
for(i=1;i<=n;i++)
for(k=1;k<=m;k++)
{
if(A[p][i][k]=='0')
{
nr=0;
i1=i;
while(A[p][i1][k]=='0' && i1>=1)
{
nr++;
i1--;
}
Nr[i][k]=nr;
}
else Nr[i][k]=0;
}
vf=-1;
for(k=1;k<=n;k++)
{
a[0].h=a[0].j=0;
a[m+1].h=a[m+1].j=0;
stiva[++vf]=a[0];
a[1].h=Nr[k][1];
a[1].j=1;
stiva[++vf]=a[1];
for(i=2;i<=m+1;i++)
{
a[i].h=Nr[k][i];
a[i].j=i;
x=a[i].h;
if(stiva[vf].h>x)
{
while(stiva[vf].h>x)
{
arie=stiva[vf].h*(a[i].j-stiva[vf].j);
if(arie>ariemax) ariemax=arie;
vf--;
}
stiva[++vf]=a[i];
}
else
if(stiva[vf].h<x)
stiva[++vf]=a[i];
}
while(vf>=0)
{
arie=stiva[vf].h*(m-stiva[vf].j);
if(arie>ariemax) ariemax=arie;
vf--;
}
vf=-1;
stiva[++vf]=a[m+1];
a[m].j=1;
stiva[++vf]=a[m];
for(i=m-1;i>=0;i--)
{
a[i].j=m-i+1;
x=a[i].h;
if(stiva[vf].h>x)
{
while(stiva[vf].h>x)
{
arie=stiva[vf].h*(a[i].j-stiva[vf].j);
if(arie>ariemax) ariemax=arie;
vf--;
}
stiva[++vf]=a[i];
}
else
if(stiva[vf].h<x)
stiva[++vf]=a[i];
}
while(vf>=0)
{
arie=stiva[vf].h*(m-stiva[vf].j);
if(arie>ariemax) ariemax=arie;
vf--;
}
}
return ariemax;
}
inline int Solutie(int lin,int col)
{
int i,j,na,nb,ma,mb,rez;
na=lin;
ma=col;
if(col==m)
{
for(i=1;i+lin<=n;i++)
for(j=1;j<=m;j++)
A[1][i][j]=mat[i+lin][j];
nb=n-lin;
mb=m;
}
else
{
for(i=1;i<=n;i++)
for(j=1;j+col<=m;j++)
A[1][i][j]=mat[i][j+col];
nb=n;
mb=m-col;
}
rez=ArieMax(0,na,ma);
rez+=ArieMax(1,nb,mb);
return rez;
}
int main()
{
int i,j;
ifstream fin("bmatrix.in");
fin>>n>>m;
for(i=1;i<=n;i++)
{
fin>>(mat[i]+1);
for(j=1;j<=m;j++)
A[0][i][j]=mat[i][j];
}
fin.close();
for(i=1;i<n;i++)
sol=max(sol,Solutie(i,m));
for(i=1;i<m;i++)
sol=max(sol,Solutie(n,i));
ofstream fout("bmatrix.out");
fout<<sol<<"\n";
fout.close();
return 0;
}