Cod sursa(job #1437375)

Utilizator BLz0rDospra Cristian BLz0r Data 17 mai 2015 16:00:05
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define Nmax 18
#define inf 0x3f3f3f3f

FILE *f = fopen ( "flip.in", "r" );
FILE *g = fopen ( "flip.out", "w" );

int v[Nmax][Nmax], N, M, rez = -inf;

void TotalSum (){ //calc suma totala din matrice
    int sum = 0;

    for ( int i = 1; i <= N; ++i )
        for ( int j = 1; j <= M; ++j )
            sum += v[i][j];

    rez = max ( rez, sum ); // si actualizez maximul

}

//flipuiesc linia ind
void FlipLine ( int ind ){
    for ( int i = 1; i <= M; ++i )
        v[ind][i] *= -1;
}

//flipuiesc coloana ind
void FlipCol ( int ind ){
    for ( int i = 1; i <= N; ++i )
        v[i][ind] *= -1;
}

//fac suma pe coloana ind
int SumaCol ( int ind ){
    int sum = 0;

    for ( int i = 1; i <= N; ++i )
        sum += v[i][ind];

    return sum;
}

//flipuiesc coloanele cu suma negativa
void CheckCols (){
    for ( int i = 1; i <= M; ++i )
        if ( SumaCol ( i ) < 0 )
            FlipCol(i);
}

//generez toate modalitatile de a flipui linii si ajustez coloanele dupa ele
void Back ( int line ){

    for ( int i = 0; i <= 1; ++i ){
        if ( !i ){ // NU flipuiesc linia line
            CheckCols(); //ajustez coloanele
            TotalSum(); //verific daca e sol mai buna
            if ( line < N )
                Back ( line + 1 );
        }
        else{ // flipuiesc linia line
            FlipLine ( line ); // flipuiesc linia
            CheckCols();//ajustez coloanele
            TotalSum();//verific daca e sol mai buna
            if ( line < N )
                Back ( line + 1 );
        }
    }
}


int main(){

    fscanf ( f, "%d%d", &N, &M );

    for ( int i = 1; i <= N; ++i )
        for ( int j = 1; j <= M; ++j )
            fscanf ( f, "%d", &v[i][j] );


    fprintf ( g, "%d", rez );

    return 0;
}