Cod sursa(job #1807994)

Utilizator KanghuAndre Popescu Kanghu Data 17 noiembrie 2016 10:21:22
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <fstream>

using namespace std;

int N, M;
int mx;
int mat[17][17];

void flip(int x, int y)
{
      if(x == 1)
      {
            for(int a = 0; a < M; a++)
            {
                  mat[y][a] = mat[y][a] * (-1);
            }
      }

      else
      {
            for(int a = 0; a < N; a++)
            {
                  mat[a][y] = mat[a][y] * (-1);
            }
      }
}

int sum()
{
      int s = 0;

      for(int a = 0; a < N; a++)
      {
            for(int b = 0; b < M; b++)
            {
                  s = s + mat[a][b];
            }
      }

      return s;
}

int backtrack(int x)
{
      if(x == N)
      {
            int k = sum();

            if(k > mx)
                  mx = k;
      }

      else
      {
            flip(1, x);
            backtrack(x + 1);

            for(int a = 0; a < M; a++)
            {
                  flip(2, a);
                  backtrack(x + 1);
            }

            flip(1, x);
            backtrack(x + 1);

            for(int a = 0; a < M; a++)
            {
                  flip(2, a);
                  backtrack(x + 1);
            }
      }
}

int main()
{
    ifstream i("flip.in");
    ofstream o("flip.out");

    i >> N >> M;

    for(int a = 0; a < N; a++)
    {
          for(int b = 0; b < M; b++)
          {
                i >> mat[a][b];
          }
    }

      backtrack(0);

      o << mx;
    return 0;
}