Pagini recente » Cod sursa (job #864729) | Cod sursa (job #1864661) | Cod sursa (job #1286902) | Cod sursa (job #38980) | Cod sursa (job #3263191)
/*
FLIP
*/
#include <iostream>
#define SIZE 20
#define FIN "flip.in"
#define FOUT "flip.out"
int stack[ SIZE ],
n,
m,
level,
suma_max = 0,
matrix[SIZE][SIZE],
_matrix[SIZE][SIZE];
using namespace std;
void readdata() {
freopen(FIN,"r",stdin);
cin>>n>>m;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j ) {
cin>>matrix[i][j];
}
}
fclose(stdin);
}
void solve_problem_flip() {
int s,
stotal = 0;
//facem o copie a matricei originale
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
_matrix[i][j] = matrix[i][j];
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(stack[ i ] == 1) {
_matrix[i][j] *= -1;
}
}
}
for(int j = 1; j <= m; ++j) {
s = 0;
for(int i = 1; i <= n; ++i) s += _matrix[i][j];
//daca suma pe coloana este negativa facem flip pe coloana respectiva
if(s < 0) s *= -1;
stotal = stotal + s;
}
if( suma_max < stotal ) suma_max = stotal;
}
void init() {
stack[ level ] = -1;
}
int succ() {
if(stack[level]<1) {
stack[level]++;
return 1;
}
return 0;
}
int sol() {
return level == n;
}
int valid() {
return 1;
}
void print() {
int flag = 0;
for(int i = 1; i <= n; ++i) {
if(stack[i] == 1) {
printf("%d ",i);
flag = 1;
}
}
if(flag == 1) printf("\n");
}
void writedata() {
freopen(FOUT, "w", stdout);
cout<<suma_max;
fclose(stdout);
}
void bkt() {
int s, v;
level = 1;
init();
while( level > 0 ) {
s = 1;//succesor
v = 0;//valid
while( s && !v ) {
s = succ();
if( s ) v = valid();
}
//daca avem succesor
if( s ) {
if(sol()) {
/*
dava avem 3 linii => subset = ({1}, {2}, {3}, {1,3}, {2,3}, {1,2}, {1,2,3})
{2,3} fac flip pe linia 2 si 3
{1,2,3} fac flip pe toate linia 1, linia 2, linia 3
*/
solve_problem_flip();
} else {
level++;
init();
}
} else { level--; }
}
}
int main(int argc, char const *argv[]) {
readdata();
bkt();
writedata();
return 0;
}