Cod sursa(job #3263186)

Utilizator M132M132 M132 M132 Data 13 decembrie 2024 19:37:03
Problema Jocul Flip Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
/*
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;
}