Pagini recente » Cod sursa (job #2439012) | Cod sursa (job #2542161) | Cod sursa (job #320545) | Cod sursa (job #899111) | Cod sursa (job #3263186)
/*
FLIP
*/
#include <iostream>
#define SIZE 20
#define FIN "flip.in"
#define FOUT "flip.out"
int stack[ 100 ],
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) {
_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 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;
}