Cod sursa(job #496972)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 31 octombrie 2010 19:05:46
Problema BMatrix Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include<cstdio>
const int N=1<<8;
int n,m,a[N][N],st[N][N],su[N][N],dsu[N][N],dst[N][N];
void read()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    scanf("%d%d\n",&n,&m);
    char s[N];
    for(int i=1;i<=n;i++)
    {
        gets(s);
        for(int j=1;j<=m;j++)
            a[i][j]=s[j-1]-'0';
    }
}
void init()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]==0)
            {
                st[i][j]=st[i][j-1]+1;
                su[i][j]=su[i-1][j]+1;
            }
}
int min(int x,int y)
{
    return (x<y && x)?x:y;
}
int getmat(int ax,int ay,int bx,int by)
{
    int max=-1;
    for(int j=ay;j<=by;j++)
        if(a[ax][j]==0)
        {
            dsu[ax][j]=1;
            dst[ax][j]=min(st[ax][j],j-ay+1);
            if(dsu[ax][j]*dst[ax][j]>max)
                max=dsu[ax][j]*dst[ax][j];

        }
    for(int i=ax;i<=bx;i++)
        if(a[i][ay]==0)
        {
            dsu[i][ay]=min(su[i][ay],i-ax+1);
            dst[i][ay]=1;
            if(dsu[i][ay]*dst[i][ay]>max)
                max=dsu[i][ay]*dst[i][ay];
        }
    for(int i=ax+1;i<=bx;i++)
        for(int j=ay+1;j<=by;j++)
            if(a[i][j]==0)
            {
                if(st[i][j]>1)
                    dsu[i][j]=min(dsu[i-1][j-1]+1,min(su[i][j],i-ax+1));
                    else dsu[i][j]=min(su[i][j],i-ax+1);
                if(su[i][j]>1)
                    dst[i][j]=min(dst[i-1][j-1]+1,min(st[i][j],j-ay+1));
                    else dst[i][j]=min(st[i][j],j-ay+1);
                if(dsu[i][j]*dst[i][j]>max)
                    max=dsu[i][j]*dst[i][j];
            }

    return max;
}
void solve()
{
    int max=-1,x,y;
    for(int i=2;i<=n;i++)
    {
        x=getmat(1,1,i-1,m);
        y=getmat(i,1,n,m);
        if(x+y>max)
            max=x+y;
    }
    for(int j=2;j<=m;j++)
    {
        x=getmat(1,1,n,j-1);
        y=getmat(1,j,n,m);
        if(x+y>max)
            max=x+y;
    }
    printf("%d",max);
}
void afis(int a[N][N])
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            printf("%d",a[i][j]);
        printf("\n");
    }
}
int main()
{
    read();
    init();
    solve();
    return 0;
}