Cod sursa(job #333680)

Utilizator cezarbotolanbotolan cezar cezarbotolan Data 23 iulie 2009 15:32:15
Problema BMatrix Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 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,&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;
    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;
        }
    }

}

void solve()
{
	int i,maxim;

	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;
}