Pagini recente » Cod sursa (job #2633298) | Cod sursa (job #2822003) | Cod sursa (job #434295) | Cod sursa (job #2647675) | Cod sursa (job #2443636)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int n, m, a[17][17], maxS = -999999999, v[2] = {-1, 1}, currentS;
void citire(int &n, int &m, int a[][17]) {
f >> n >> m;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
f >> a[i][j];
///fiecare linie si coloana are la sfarsit cate un element care memoreaza daca linia/coloana e flipped sau nu
for(int i = 0; i < n; i++)
a[i][m] = 1;
for(int i = 0; i < m; i++)
a[n][i] = 1;
}
///la fel functioneaza si functia sum
int sum(int lc) {
int s = 0;
if(lc < n)
for(int i = 0; i < m; i++)
s += a[lc][i];
else
for(int i = 0; i < n; i++)
s +=a[i][lc-n];
return s;
}
///functia flip schimba elementele de pe o linie (linia lc) daca lc < n(nr de lniii din matrice)
/// sau schimba elementele de pe coloana lc - n daca lc >= n
void flip(int lc) {
currentS -= 2*sum(lc);
if(lc < n) {
for(int i = 0; i <= m; i++)
a[lc][i] = -a[lc][i];
} else {
for(int i = 0; i <= n; i++)
a[i][lc-n] = -a[i][lc-n];
}
}
///folosind acelasi rationament ca in functia flip, functia isFlipped returneaza 1 daca linia lc/coloana lc-n este flipped sau -1 in caz contrar
int isFlipped(int lc) {
if(lc < n)
return a[lc][m];
else
return a[n][lc-n];
}
int Msum(int a[][17]) {
int s = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
s+= a[i][j];
return s;
}
void backtracking(int k) {
for(int i = 0; i <= 1; i++) {
if(isFlipped(k) != v[i]) {
flip(k);
//cout << "flip " << k << '\n';
if(currentS > maxS) {
maxS = currentS;
//cout << maxS <<'\n';
}
}
if(k < m+n-1)
backtracking(k+1);
}
}
int main() {
citire(n, m, a);
maxS = Msum(a);
currentS = Msum(a);
backtracking(0);
g << maxS;
}