Cod sursa(job #1216220)

Utilizator veronica.velciuVelciu Veronica-Mihaela veronica.velciu Data 3 august 2014 19:07:34
Problema Jocul Flip Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
/* 
 * File:   main.cpp
 * Author: veronica
 *
 * Created on August 3, 2014, 12:51 PM
 */

#include <cstdlib>
#include <fstream>

int n, m;
int table[16][16];
int max;

int sol[16];

int get_sum() {
    int s = 0;
    
    for(int i = 0; i < n; i++) {
        int line = 0;
        for(int j = 0; j < m; j++) {
            line += sol[j] * table[i][j];
        }
        if(line > 0)
            s += line;
        else
            s -= line;
    }
    
    return s;
}

void bt(int step) {
    if(step == n) {
        int sum = get_sum();

        if(sum > max) {
            max = sum;
        }
    }
    else {
        bt(step + 1);

        sol[step] = -1;

        bt(step + 1);
        
        sol[step] = 1;
    }
}

int main(int argc, char** argv) {
    std::ifstream in("flip.in", std::ifstream::in);
    std::ofstream out("flip.out", std::ofstream::out);
    
    in>>n>>m;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            in>>table[i][j];
        }
    }
    
    for(int i = 0; i < 16; i++) {
        sol[i] = 1;
    }
    
    max = -256000000;
    bt(0);
    
    out<<max;
    
    in.close();
    out.close();
    
    return 0;
}