Cod sursa(job #1423967)

Utilizator RaresCRares Cristian RaresC Data 23 aprilie 2015 00:34:03
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#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;
}