Cod sursa(job #496954)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 31 octombrie 2010 17:49:42
Problema BMatrix Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 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[1][j]==0)
        {
            dsu[1][j]=1;
            dst[1][j]=min(st[1][j],j-ay+1);
        }
    for(int i=ax;i<=bx;i++)
        if(a[i][1]==0)
        {
            dsu[i][1]=min(su[i][1],i-ax+1);
            dst[i][1]=1;
        }
    for(int i=ax+1;i<=bx;i++)
        for(int j=ay+1;j<=by;j++)
            if(a[i][j]==0)
            {
                dsu[i][j]=min(dsu[i-1][j-1]+1,min(su[i][j],i-ax+1));
                dst[i][j]=min(dst[i-1][j-1]+1,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 resetl(int x)
{
    for(int j=1;j<=m;j++)
         dsu[x][j]=dst[x][j]=0;
}
void resetc(int y)
{
    for(int i=1;i<=n;i++)
        dsu[i][y]=dst[i][y]=0;
}
void solve()
{
    int max=-1,x,y;
    for(int i=2;i<=n;i++)
    {
        x=getmat(1,1,i-1,m);
        resetl(i-1);
        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);
        resetc(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;
}