Cod sursa(job #3157907)

Utilizator ifrim.claudiaClaudia Ifrim ifrim.claudia Data 17 octombrie 2023 12:43:02
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb
// Gigel a descoperit un nou joc pe care l-a numit "Flip".
// Acesta se joaca pe o tabla dreptunghiulara de dimensiuni N*M care contine numere intregi.
// Fiecare linie si fiecare coloana are un comutator care schimba starea tuturor elementelor
// de pe acea linie sau coloana, inmultindu-le cu -1. Scopul jocului este ca pentru o
// configuratie data a tablei de joc sa se actioneze asupra liniilor si coloanelor astfel
// incat sa se obtina o tabla cu suma elementelor cat mai mare.
// Dandu-se o configuratie pentru tabla "Flip",
// realizati un program care sa determine suma maxima pe care Gigel o poate obtine.

// ### Date de intrare

// Prima linie a fisierului flip.in contine doua numere intregi N si M, separate prin cate un spatiu,
// care reprezinta dimensiunea tablei. Urmatoarele N linii contin cate M numere intregi seperate
// prin cate un spatiu care descriu configuratia tablei de joc.

// ### Date de iesire

// Prima linie a fisierului flip.out contine un numar care va reprezenta suma maxima pe care Gigel
// o poate obtine comutand liniile si coloanele tablei de joc.

// ### Restrictii si precizari

// 1 ≤ N, M ≤ 16
// Tabla de joc contine numere intregi din intervalul [-1.000.000,1.000.000]

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("flip.in");
ofstream fout("flip.out");

int n, m, t[17][17], s[17], smax, b;

void print()
{
  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= m; j++)
    {
      cout << t[i][j] << " ";
    }
    cout << endl;
  }
}

int sum_row(int row)
{
  int s = 0;
  for (int j = 1; j <= m; j++)
  {
    s = s + t[row][j];
  }

  return s;
}

int sum_col(int col)
{
  int s = 0;
  for (int i = 1; i <= n; i++)
  {
    s = s + t[i][col];
  }

  return s;
}

void back(int k)
{
  int sum = 0;
  if (k == n + 1)
  {
    sum = 0;
    for (int i = 1; i <= m; i++)
    {
      sum = sum + abs(s[i]);
    }
    smax = max(smax, sum);
    return;
  }

  back(k + 1);

  for (int j = 1; j <= m; j++)
  {
    s[j] = s[j] - 2 * t[k][j];
  }

  back(k + 1);

  for (int j = 1; j <= m; j++)
  {
    s[j] = s[j] + 2 * t[k][j];
  }
}

int main()
{
  fin >> n >> m;
  if (n < 1 || n > 17)
  {
    return 0;
  }

  if (m < 1 || m > 17)
  {
    return 0;
  }

  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= m; j++)
    {
      fin >> t[i][j];
      s[j] = s[j] + t[i][j];
    }
  }
  fin.close();

  back(1);

  fout << smax << endl;

  fout.close();

  return 0;
}