Cod sursa(job #1740368)

Utilizator jurjstyleJurj Andrei jurjstyle Data 11 august 2016 15:17:24
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
/*
initial vom scrie varianta ineficienta .. generam toate flipurile de linii ;
din fiecare stare generam toate flipurile de coloane
si verificam
O(2^(N+M)*(N^2))
*/
#include <fstream>

using namespace std ;

ifstream f ("flip.in") ;
ofstream g ("flip.out") ;

int n , m , a[18][18] , b[18][18] ;
int linii[18] , coloane[18] , smax = -1e9 ;

void verif ()
{
 for ( int i = 1 ; i <= n ; ++i )
    if ( linii[i] )
        for ( int j = 1 ; j <= m ; ++j )
            a[i][j] *= (-1) ;
  for ( int i = 1 ; i <= m ; ++i )
    if ( coloane[i] )
        for ( int j = 1 ; j <= n ; ++j )
            a[j][i] *= (-1) ;
 int s = 0 ;
 for ( int i = 1 ; i <= n ; ++i )
    for ( int j = 1 ; j <= m ; ++j )
        s += a[i][j] ;
 if ( s > smax )
    smax = s ;
 for ( int i = 1 ; i <= n ; ++i )
    for ( int j = 1 ; j <= m ; ++j )
        a[i][j] = b[i][j] ;
}


void back2 ( int k )
{
 if ( k == m + 1 )
    verif () ;
 else
    {
     back2 ( k + 1 ) ;
     coloane[k] = 1 ;
     back2 ( k + 1 ) ;
     coloane[k] = 0 ;
    }

}

void back1 ( int k )
{
 if ( k == n + 1 )
    back2 ( 1 ) ;
 else
    {
     back1 ( k + 1 ) ;
     linii[k] = 1 ;
     back1 ( k + 1 ) ;
     linii[k] = 0 ;
    }
}



int main ()
{
 f >> n >> m ;
 for ( int i = 1 ; i <= n ; ++i )
    for ( int j = 1 ; j <= m ; ++j )
        f >> a[i][j] , b[i][j] = a[i][j] ;
 back1 ( 1 ) ;
 g << smax ;

}