Pagini recente » Cod sursa (job #1359313) | Cod sursa (job #2047450) | Cod sursa (job #12195) | Cod sursa (job #3168995) | Cod sursa (job #3157907)
// 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;
}