Cod sursa(job #373537)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 14 decembrie 2009 00:26:38
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <cstdio>

#define file_in "bmatrix.in"
#define file_out "bmatrix.out"

#define Nmax 201

int n,m;
int x1[Nmax];
int y1[Nmax];
int x2[Nmax];
int y2[Nmax];
int sc[Nmax][Nmax];
int sl[Nmax][Nmax];
int l,max;


void citire()
{
	int i,j;
	char c[Nmax];

	freopen(file_in,"r",stdin);

	scanf("%d %d\n", &n,&m);
	for (i=1;i<=n;++i)
	{
		scanf("%s\n", c+1);
		for (j=1;j<=m;++j)
		{
			sc[i][j]=sc[i-1][j]+c[j]-'0';
			sl[i][j]=sl[i][j-1]+c[j]-'0';
		}
	}
}

void ver()   
{   
	int i,j,k;
    for (i=1;i<=n;++i)   
         for (j=i;j<=n;++j)   
         {   
          l=0;   
          max=0;   
          for (k=1;k<=m;++k)   
          {   
            if (sc[j][k]==sc[i-1][k]) 
				l+=(j-i+1);   
                else 
				l=0;   
            if (l>max) max=l;   
            if (max>x1[k]) 
				x1[k]=max;   
          }   
        l=0;   
        max=0;   
        for (k=m;k>=1;k--)   
		{   
		  if (sc[j][k]==sc[i-1][k]) 
			  l+=(j-i+1);   
              else 
			  l=0;   
          if (l>max) max=l;   
          if (max>y1[k]) 
			  y1[k]=max;   
            }   
        }        
}  


void ori()
{
	int i,j,k;
	for (i=1;i<=m;++i)   
        for (j=i;j<=m;++j)   
        {   
        l=0;   
        max=0;   
        for (k=1;k<=n;++k)   
		{   
           if (sl[k][j]==sl[k][i-1]) 
			   l+=(j-i+1);   
               else 
			   l=0;   
        if (l>max) max=l;   
        if (max>x2[k]) 
			x2[k]=max;   
        }   
        l=0;   
        max=0;   
        for (k=n;k>=1;--k)   
        {   
		  if (sl[k][j]==sl[k][i-1]) 
			  l+=(j-i+1);   
              else 
			  l=0;   
        if (l>max) max=l;   
        if (max>y2[k]) 
			y2[k]=max;   
        }   
    }   

}

inline int maxx(int a, int b) { return a>b?a:b; }

void solve()
{
	int i,maxim;

/*	for(i=2;i<=n;++i)
		x1[i]=maxx(x1[i],x1[i-1]);
	for(i=n-1;i>=1;--i)
		x2[i]=maxx(x2[i],x2[i+1]);
	for(i=2;i<=m;++i)
		y1[i]=maxx(y1[i],y1[i-1]);
	for(i=m-1;i>=1;--i)
		y2[i]=maxx(y2[i],y2[i+1]);*/
	
	maxim=0;
	for (i=1;i<=n;++i)
		 if (x1[i]+y1[i+1]>maxim)
			 maxim=x1[i]+y1[i+1];
	for (i=1;i<=m;++i)
		 if (x2[i]+y2[i+1]>maxim)
			 maxim=x2[i]+y2[i+1];
	freopen(file_out,"w",stdout);
	printf("%d", maxim);


}

int main()
{
	citire();
	ver();
	ori();
    solve();

	fclose(stdin);
	fclose(stdout);

	return 0;
}