Cod sursa(job #333602)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 23 iulie 2009 12:40:29
Problema BMatrix Scor 0
Compilator cpp Status done
Runda splunge4 Marime 2.9 kb
# include <algorithm>
using namespace std;

# define DIM 201

int n, m, rez, max0, max1, a[ DIM ][ DIM ], z[ DIM ][ DIM ];

void init () {

    int i, j;

    for ( i = 1; i <= n; ++ i )
        for ( j = 1; j <= m; ++ j )
            z[ i ][ j ] = 0;
}

void solve () {

    int c, i, j, k, l, zero;
    char s[ DIM ];

    scanf ( "%d%d\n", &n, &m );
    for ( i = 1; i <= n; ++ i ) {

            gets ( s );
            for ( j = 1; j <= m; ++ j )
                a[ i ][ j ] = s[ j - 1 ] - '0';
    }
    for ( l = 2; l <= n; ++ l ) {

        init ();
        max0 = max1 = 0;
        for ( i = 1; i < l; ++ i )
            for ( j = 1; j <= m; ++ j )
                if ( !a[ i ][ j ] ) {

                    if ( !a[ i ][ j - 1 ] )
                        z[ i ][ j ] = z[ i ][ j - 1 ] + 1;
                    else
                        z[ i ][ j ] = 1;
                    zero = z[ i ][ j ];
                    for ( k = i; k > 0; -- k )
                        max0 = max ( max0, ( i - k + 1 ) * min ( zero, z[ k ][ j ] ) );
                }
        for ( i = l; i <= n; ++ i )
            for ( j = 1; j <= m; ++ j )
                if ( !a[ i ][ j ] ) {

                    if ( !a[ i ][ j - 1 ] )
                        z[ i ][ j ] = z[ i ][ j - 1 ] + 1;
                    else
                        z[ i ][ j ] = 1;
                    zero = z[ i ][ j ];
                    for ( k = i; k >= l; -- k )
                        max1 = max ( max1, ( i - k + 1 ) * min ( zero, z[ k ][ j ] ) );
                }
        if ( max0 + max1 > rez )
            rez = max0 + max1;
    }
    for ( c = 2; c <= m; ++ c ) {

        init ();
        max0 = max1 = 0;
        for ( i = 1; i <= n; ++ i )
            for ( j = 1; j < l; ++ j )
                if ( !a[ i ][ j ] ) {

                    if ( !a[ i ][ j - 1 ] )
                        z[ i ][ j ] = z[ i ][ j - 1 ] + 1;
                    else
                        z[ i ][ j ] = 1;
                    zero = z[ i ][ j ];
                    for ( k = i; k > 0; -- k )
                        max0 = max ( max0, ( i - k + 1 ) * min ( zero, z[ k ][ j ] ) );
                }
        for ( i = 1; i <= n; ++ i )
            for ( j = l; j <= m; ++ j )
                if ( !a[ i ][ j ] ) {

                    if ( !a[ i ][ j - 1 ] )
                        z[ i ][ j ] = z[ i ][ j - 1 ] + 1;
                    else
                        z[ i ][ j ] = 1;
                    zero = z[ i ][ j ];
                    for ( k = i; k >= l; -- k )
                        max1 = max ( max1, ( i - k + 1 ) * min ( zero, z[ k ][ j ] ) );
                }
        if ( max0 + max1 > rez )
            rez = max0 + max1;
    }
    printf ( "%d", rez );
}

int main () {

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

    solve ();

    return 0;
}