Cod sursa(job #494519)

Utilizator zooppAccount deletion pending zoopp Data 21 octombrie 2010 20:57:16
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <cstdio>
#include <list>

using namespace std;

int sum(int (*matr)[16], int &row, int &line);
void back(int (*matr)[16], int &row, int &line, bool *truthTable, int &solution,int index);
void flip(int (*matr)[16], int &row, int &line, int index, char c);

int main()
{
    int matr[16][16];
    bool truthTable[16];
    int row;
    int line;
    int max = 0;
    
    FILE *input = fopen("flip.in", "r");
    FILE *output = fopen("flip.out", "w");
    
    if (input != NULL) {
        fscanf(input, "%d %d", &row, &line);
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < line; j++) {
                fscanf(input, "%d", &matr[i][j]);
            }
        }
    }
    
    back(matr, row, line, truthTable, max, 0);

    fprintf(output,"%d", max);
    return 0;
}

int sum(int (*matr)[16], int &row, int &line)
{
    int tempSum = 0;
    
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < line; j++) {
                tempSum += matr[i][j]; 
        }
    }
    return tempSum;
}

void back(int (*matr)[16], int &row, int &line, bool *truthTable, int &solution, int index)
{
    if (index == row + line-1) {
        for (int i = 0; i < row; i++) {
            if (truthTable[i]) {
                    flip(matr, row, line, i, 'r');
            }
        }
        for (int i = 0; i < line; i++) {
            if (truthTable[row + i]) {
                flip(matr, row, line, i, 'l');
            }
        }
        
        int tempSum = sum(matr, row, line);
        if (tempSum > solution) {
            solution = tempSum;
        }
        return;
    }
    
    truthTable[index] = false;
    back(matr, row, line, truthTable, solution, index + 1);
    truthTable[index] = true;
    back(matr, row, line, truthTable, solution, index + 1);
}

void flip(int (*matr)[16], int &row, int &line, int index, char c)
{
    switch (c) {
        case 'r':
            for (int i = 0; i < row; i++) {
                matr[i][index] *= -1;
            }
            break;
        case 'l':
            for (int i = 0; i < line; i++) {
                matr[index][i] *= -1;
            }
            break;
    }
}