Pagini recente » Cod sursa (job #697304) | Cod sursa (job #871908) | Cod sursa (job #2113672) | Cod sursa (job #2698617) | Cod sursa (job #1740368)
/*
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 ;
}