Cod sursa(job #323651)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 12 iunie 2009 23:19:07
Problema BMatrix Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <cstdio>

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

#define Nmax 210

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


void citire()
{
	int i,j;
	char c[Nmax];
	
	freopen(file_in,"r",stdin);
	
	scanf("%d %d", &n,&m);
	for (i=1;i<=n;++i)
	{
		fgets(c,Nmax,stdin);
		for (j=1;j<=m;++j)
		{
			sc[i][j]=sc[i-1][j]+c[j-1]-'0';
			sl[i][j]=sl[i][j-1]+c[j-1]-'0';
		}
	}
}

void ver()
{
	int i,j,k,max,l;
	for (i=1;i<=n;++i)
	     for (j=i;j<=n;++j)
		 {
			l=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=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,l,max;
	for (i=1;i<=m;++i)
	     for (j=i;j<=m;++j)
		 {
			l=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=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; 
			}			
		 }
}

void solve()
{
	int i,maxim;
	
	maxim=0;
	/*for (i=1;i<=n;++i)
		 printf("%d ", x1[i]);
	printf("\n");
	for (i=1;i<=n;++i)
		 printf("%d ", y1[i]);
	printf("\n");
	for (i=1;i<=m;++i)
		 printf("%d ", x2[i]);
	printf("\n");
	for (i=1;i<=m;++i)
		 printf("%d ", y2[i]);*/
	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;
}