Nu aveti permisiuni pentru a descarca fisierul grader_test11.in
Cod sursa(job #333617)
Utilizator | Data | 23 iulie 2009 13:01:06 | |
---|---|---|---|
Problema | BMatrix | Scor | 8 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.54 kb |
#include<stdio.h>
#define DIM 201
int a[DIM][DIM],b[DIM][DIM],n,m;
int solve (int x1,int y1,int x2,int y2)
{
int i,j,d1=0,d2=0,d3=0,max=0;
for(i=x1;i<=x2;++i)
for(j=y1;j<=y2;++j)
{
d1=b[i-1][j-1];
d2=b[i-1][j];
d3=b[i][j-1];
if(a[i-1][j-1]==-1 || i==x1 || j==y1)
d1=0;
if(a[i-1][j]==-1 || i==x1)
d2=0;
if(a[i][j-1]==-1 || j==y1)
d3=0;
if(a[i][j]==-1)
b[i][j]=-1;
else
b[i][j]=d2+d3+1-d1;
if(max<b[i][j])
max=b[i][j];
}
return max;
}
void refresh ()
{
int i,j;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
b[i][j]=a[i][j];
}
int main ()
{
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
int i,j,max=0,sum;
char ch;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
{
scanf("\n");
for(j=1;j<=m;++j)
{
scanf("%c",&ch);
if(ch=='0')
a[i][j]=0;
else
a[i][j]=-1;
}
}
for(i=1;i<n;++i)
{
refresh ();
sum=solve(1,1,n-i,m)+solve(n-i+1,1,n,m);
if(max<sum)
max=sum;
}
for(i=1;i<m;++i)
{
refresh ();
sum=solve(1,1,n,m-i)+solve(1,m-i+1,n,m);
if(max<sum)
max=sum;
}
printf("%d",max);
return 0;
}