Cod sursa(job #52101)

Utilizator 004444Lapusan Tudor 004444 Data 17 aprilie 2007 19:18:00
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <stdio.h>
#define MAX 17


int n, m, sol_max;
int lin[MAX], col[MAX];
int a[MAX][MAX], b[MAX][MAX];


void citire ();
void solve ();
void back1 ( int i );
void back2 ( int i );
void flip ();
void afisare ();


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

    citire ();
    solve ();
    afisare ();

    return 0;
}

void citire ()
{
    int i, j;

    scanf ( "%d %d", &n, &m );
    for ( i = 1; i <= n; i++ )
        for ( j = 1; j <= m; j++ )
            scanf ( "%d", &a[i][j] );
/*
    for ( i = 1; i <= n; i++ )
    {
        for ( j = 1; j <= m; j++ )
            printf ( "%d ", a[i][j] );
        printf ( "\n" );
    }
*/
}

void solve ()
{
    sol_max = -2000000000;

    back1 ( 1 );
}

void back1 ( int l1 )
{
    int i, j;

    for ( j = 1; j <= n; j++ )
        lin[j] = 0;

    for ( i = 0; i <= 1; i++ )
    {
        lin[l1] = i;

        back2 ( 1 );
        if ( l1 < n )
            back1 ( l1 + 1 );
    }
}

void back2 ( int c1 )
{
    int i, j;  
        
    for ( j = 1; j <= m; j++ )
        col[j] = 0;

    for ( i = 0; i <= 1; i++ )
    {
        col[c1] = i;

        flip ();
        if ( c1 < m )
            back2 ( c1 + 1 );
    }
}

void flip ()
{
    int i, j, s;

    for ( i = 1; i <= n; i++ )
        if ( lin[i] == 1 )
            for ( j = 1; j <= m; j++ )
                b[i][j] = a[i][j] * (-1);
        else
            for ( j = 1; j <= m; j++ )
                b[i][j] = a[i][j];

    for ( i = 1; i <= m; i++ )
        if ( col[i] == 1 )
            for ( j = 1; j <= n; j++ )
                b[j][i] = a[j][i] * (-1);
            else
                b[j][i] = a[j][i];       

    s = 0;
    for ( i = 1; i <= n; i++ )
    {
        for ( j = 1; j <= m; j++ )
            s += b[i][j];
    }
//            printf ( "%d ", b[i][j] );
//        printf ( "\n" );
//    }
//    printf ( "\n" );

    if ( s > sol_max )
        sol_max = s;
}     
        
void afisare ()
{
    printf ( "%ld\n", sol_max );
}