/*
C
C 4 -2 2
3 -1 5
2 0 -3
4 1 -3
5 -3 2
C -4 2 -2
3 -1 5
2 0 -3
4 1 -3
5 -3 2
C 4 -2 2
-3 -1 5
-2 0 -3
-4 1 -3
-5 -3 2
5 linii => trebuie sa generam toate submultimile de linii
3 linii si 3 coloane
M = {1,2,3}, n = 3
2^n
2^3 = submultimi
Subset = ({1},{2},{3},{1,3},{2,3},{1,2},{1,2,3})
facem FLIP pe rand:
1.linia 1
2.linia 2
3.linia 3
4.linia 1 si linia 3
5.linia 2 si linia 3
6.linia 1 si linia 2
7.liniile 1, 2 ,3
Backtracking
4 -2 2
3 -1 5
2 0 -3
4 1 -3
5 -3 2
*/
#include <iostream>
#define FIN "flip.in"
#define FOUT "flip.out"
#define SIZE 20
using namespace std;
int stack[ SIZE ],
level,
n,//numarul de linii
m,//numarul de coloane
sum_max = 0,//variabila globala
matrix[SIZE][SIZE],
_matrix[SIZE][SIZE];
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 writeData() {
/*
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cout<<matrix[i][j]<<" ";
}
cout<<"\n";
}
*/
freopen(FOUT,"w",stdout);
cout<<sum_max;
fclose(stdout);
}
void init() {
stack[level] = -1;
}
// 1 2 3 4 5
//stack = [0,0,1]
//stack = [0,1,1]
//stack = [1,0,1]
//stack = [1,1,1]
///level = 1,2,3
int succ() {
if(stack[level]<1) {
stack[level]++;
return 1;
}
return 0;
}
int valid() {
return 1;
}
int sol() {
return level == n;
}
/*
void display() {
for(int i = 1; i <= n; ++i) {
if(stack[i] == 1) {
cout<<i<<" ";
}
}
cout<<"\n";
}
*/
void solve_problem_flip() {
int s,
stotal = 0;
//facem o copie a matricei
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
_matrix[i][j] = matrix[i][j];
}
}
//in stack[i] stocam o submultime de linii
//stack = {1,2}
//stack = {1,3}
//stack = {2,3}
//stack = {1}{2},{3}
//stack = {1}
//stack = {2}
//stack = {3}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j)
if( stack[i] == 1 ) {
//facem flip pe linia stack[i]
_matrix[i][j] *= -1;
}
}
for(int j = 1; j <= m; ++j) {
s = 0;
for(int i = 1; i <= n; i++) {
s = s + _matrix[i][j];
}
//daca suma pe coloana este negativa facem flip pe coloana respectiva
if(s < 0) s*=-1;
stotal = stotal + s;
}
if(sum_max<stotal) sum_max = stotal;
}
void bk() {
//s de la succesor
//v de la valid
int s, v;
level = 1;
init();
while(level>0) {
s = 1;
v = 0;
while(s && !v)
{
s = succ();
if(s) v = valid();
}
if(s)
{
if( sol() )
{
//aici avem putem sa apelam functia solve
solve_problem_flip();
} else {
level++;
init();
}
}
else
{
level--;
}
}
}
/*
level = 1
stack[level] = -1, stack[level]++
stack nivelul 3: 1 stack[nivel]++ adica -1+1 , facem stack[level]++ 1
stack nivelul 2: 1 stack[nivel]++ adica -1+1
stack nivelul 1: 1 stack[nivel]++ adica -1+1
cand ajunge la 1 1 1 iese din while pentru ca level trebuie sa fie > 0
apelez init()
*/
int main(int argc, char const *argv[]) {
readData();
bk();
writeData();
//Submultimile unei multimi: 2^n = 2^3 = 8 submultimi
//multimea vida
//1: 001 plus 001 {1}
// 321
//2: 010 plus 001 binar {2}
//3: 011 {1,2}
//4: 100 {3}
//5: 101 {1,3}
//6: 110 {3,2}
//7: 111 {3,2,1}
// 001 = {1}
// stack = [0,0,1]
// stack = [1,0,1]
// Backtracking fara bitwise
//alta varianta de generare
//cu 4 linii de cod cu operatorul bitwise & logic
return 0;
}
/*
1 2 3
-3 2 3
-4 2 3
matrix devine:
-1 2 3
3 2 3
4 2 3
Sum pe coloana 1 = 1 + (-3) + (-4) = 1 - 3 - 4 = 1 - 7 = -6
flip la suma
*/