Pagini recente » Cod sursa (job #1491544) | Cod sursa (job #2161851) | Cod sursa (job #811099) | Cod sursa (job #944206) | Cod sursa (job #1423967)
#include <iostream>
#include <fstream>
using namespace std;
#define MAX 16
int W, H;
int solution;
int board[MAX][MAX];
void row_flip(int r) {
for (int i = 0; i < W; i++)
board[r][i] *= -1;
}
void column_flip(int c) {
for (int i = 0; i < H; i++)
board[i][c] *= -1;
}
int solve_cur_board() {
int sum = 0;
// for each row, optimum solution is independent of every other row.
for (int i = 0; i < H; i++) {
int sum1 = 0;
for (int k = 0; k < W; k++)
sum1 += board[i][k];
int sum2 = 0;
row_flip(i); // is it better as it is, or if we flipped the row?
for (int k = 0; k < W; k++)
sum2 += board[i][k];
// reset the board. - undo the change.
row_flip (i);
sum += max(sum1, sum2);
}
return sum;
}
void column_permutation(int c) {
if (c == W) {
solution = max (solution, solve_cur_board());
return;
}
for (int i = 0; i < 2; i++) {
if (i == 0) column_flip(c);
c++;
column_permutation(c);
c--;
if (i == 0) column_flip(c);
}
}
int main() {
ifstream fin ("flip.in");
ofstream fout ("flip.out");
fin >> H >> W;
for (int i = 0; i < H; i++)
for (int k = 0; k < W; k++)
fin >> board[i][k];
column_permutation(0);
fout << solution << "\n";
return 0;
}