Cod sursa(job #3184017)

Utilizator thinkphpAdrian Statescu thinkphp Data 13 decembrie 2023 22:59:39
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 4.1 kb
/*
  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
*/