Cod sursa(job #12628)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 4 februarie 2007 15:25:36
Problema BMatrix Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>

#define maxn 210

char a[maxn][maxn],b[maxn][maxn];
int n,m,sol;
int o[maxn][maxn],u[maxn][maxn],v[maxn][maxn],c[maxn][maxn];
int d1[maxn],d2[maxn];

void rotate()
{
     int i,j,aux;
     
     for (i=0;i<m;i++)
       for (j=0;j<n;j++) 
         b[i][j]=a[n-j-1][i];
         
     aux=n;
     n=m;
     m=aux;
     
     for (i=0;i<n;i++)
       for (j=0;j<m;j++) a[i][j]=b[i][j];
}

void symetric()
{
     int i,j,aux;
     
     for (i=0;i<n;i++)
       for (j=0;j<m/2;j++)
       {
           aux=a[i][j];
           a[i][j]=a[i][m-j-1];
           a[i][m-j-1]=aux;
       }
}

void solve()
{
     int i,j;
     
     for (i=0;i<m;i++) d1[i]=0;
         
     for (i=0;i<n;i++) 
       if (a[i][0]=='1') o[i][0]=0;
       else o[i][0]=1;
       
     for (i=0;i<n;i++)
       for (j=1;j<m;j++)
         if (a[i][j]=='1') o[i][j]=0;
         else o[i][j]=o[i][j-1]+1;
         
     for (j=0;j<m;j++) 
       if (o[0][j]>0) v[0][j]=1;
       else v[0][j]=0;
     
     for (i=1;i<n;i++)
       for (j=0;j<m;j++) 
         if (o[i-1][j]>=o[i][j]) v[i][j]=v[i-1][j]+1;
		 else v[i][j]=1;

	 for (j=0;j<m;j++)
	   if (o[n-1][j]>0) u[n-1][j]=1;
       else u[n-1][j]=0;
         
	 for (i=n-2;i>=0;i--)
       for (j=0;j<m;j++)
         if (o[i+1][j]>=o[i][j]) u[i][j]=u[i+1][j]+1;
         else u[i][j]=1;
         
     for (i=0;i<n;i++) 
       for (j=0;j<m;j++) 
       {
           c[i][j]=(v[i][j]+u[i][j]-1)*o[i][j];
           if (c[i][j]>d1[j]) d1[j]=c[i][j];
       }
       
     for (i=1;i<m;i++)
       if (d1[i-1]>d1[i]) d1[i]=d1[i-1];
}

int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    
    scanf("%d %d ",&n,&m);             
    
    int i,j;
    
    for (i=0;i<n;i++)
      fgets(a[i],maxn,stdin);
      
    solve();
    for (i=0;i<m;i++) d2[i]=d1[i];
    
    symetric();
    solve();
    
	for (i=0;i<m;i++)
      if (d2[i]+d1[m-i-2]>sol) sol=d2[i]+d1[m-i-2];
          
	rotate();

	solve();
	for (i=0;i<m;i++) d2[i]=d1[i];

	symetric();
	solve();

	for (i=0;i<m;i++)
	  if (d2[i]+d1[m-i-2]>sol) sol=d2[i]+d1[m-i-2];

	printf("%d\n",sol);

	return 0;
}