Cod sursa(job #333755)

Utilizator DraStiKDragos Oprica DraStiK Data 23 iulie 2009 18:06:41
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <stdio.h>
#define DIM 205

int a[DIM][DIM],s1[DIM][DIM],s2[DIM][DIM],f1[DIM][DIM],f2[DIM][DIM];
int n,m,rez;

void read ()
{
    char buff[DIM];
    int i,j;

    scanf ("%d%d\n",&n,&m);
    for (i=1; i<=n; ++i)
    {
        gets (buff);
        for (j=1; j<=m; ++j)
            a[i][j]=buff[j-1]-'0';
    }
}

void proc ()
{
    int i,j,k,min;

    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j)
        {
            if (!a[i][j])
            {
                min=f1[i][j]=s1[i][j]=s1[i][j-1]+1;
                for (k=i-1; k>=1 && s1[k][j]; --k)
                {
                    if (s1[k][j]<min)
                        min=s1[k][j];
                    if (min*(i-k+1)>f1[i][j])
                        f1[i][j]=min*(i-k+1);
                }
            }
            if (f1[i-1][j]>f1[i][j])
                f1[i][j]=f1[i-1][j];
            if (f1[i][j-1]>f1[i][j])
                f1[i][j]=f1[i][j-1];
            }
    for (i=n; i>=1; --i)
        for (j=m; j>=1; --j)
        {
            if (!a[i][j])
            {
                min=f2[i][j]=s2[i][j]=s2[i][j+1]+1;
                for (k=i+1; k<=n && s2[k][j]; ++k)
                {
                    if (s2[k][j]<min)
                        min=s2[k][j];
                    if (min*(k-i+1)>f2[i][j])
                        f2[i][j]=min*(k-i+1);
                }
            }
            if (f2[i+1][j]>f2[i][j])
                f2[i][j]=f2[i+1][j];
            if (f2[i][j+1]>f2[i][j])
                f2[i][j]=f2[i][j+1];
        }
}

void solve ()
{
    int i;

    for (i=1; i<=n; ++i)
        if (f1[i][m]+f2[i+1][1]>rez)
            rez=f1[i][m]+f2[i+1][1];
    for (i=1; i<=m; ++i)
        if (f1[n][i]+f2[1][i+1]>rez)
            rez=f1[n][i]+f2[1][i+1];
    printf ("%d",rez);
}

int main ()
{
    freopen ("bmatrix.in","r",stdin);
    freopen ("bmatrix.out","w",stdout);

    read ();
    proc ();
    solve ();

    return 0;
}