Pagini recente » Cod sursa (job #1085190) | Cod sursa (job #2071561) | Cod sursa (job #3137187) | Cod sursa (job #1785961) | Cod sursa (job #1751192)
#include<fstream>
#include<iostream>
#include<climits>
using namespace std;
int m, n;
int **game;
int maxSum;
ifstream f("flip.in");
ofstream g("flip.out");
void print() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << game[i][j] << "\t";
}
cout << endl;
}
}
inline void invertRow(int row) {
for (int j = 0; j < m; j++) {
game[row][j] = -game[row][j];
}
}
inline void invertCol(int col) {
for (int i = 0; i < n; i++) {
game[i][col] = -game[i][col];
}
}
int totalSum() {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
sum += game[i][j];
}
}
return sum;
}
void backtrackC(int start) {
if (start == m) {
return;
} else {
int x = totalSum();
if (x > maxSum) {
maxSum = x;
}
}
for (int i = start; i < m; i++) {
invertCol(i);
backtrackC(i + 1);
invertCol(i);
}
}
void backtrackR(int start) {
if (start == n) {
return;
} else {
backtrackC(0);
}
for (int i = start; i < n; i++) {
invertRow(i);
backtrackR(i + 1);
invertRow(i);
}
}
void backtrack() {
backtrackR(0);
}
void freeAll() {
for (int i = 0; i < n; i++) {
delete game[i];
}
delete game;
}
int main() {
f >> n >> m;
game = new int*[n];
for (int i = 0; i < n; i++) {
game[i] = new int[m];
for (int j = 0; j < m; j++) {
f >> game[i][j];
}
}
maxSum = totalSum();
backtrack();
g << maxSum;
freeAll();
return 0;
}