Cod sursa(job #2046412)

Utilizator nelsonmondialuAwala pa barosaneala nelsonmondialu Data 23 octombrie 2017 19:49:16
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");

int nrLines, nrColumns, element[20][20], sumLine[20], sumColumn[20], maxSum;

void flip(int opType, int nr) {
    if (!opType) {
        sumLine[nr] = 0;
        for (int i = 1; i <= nrColumns; ++i)
            element[nr][i] = -element[nr][i],
            sumLine[nr] += element[nr][i];
    }
    else {
        sumColumn[nr] = 0;
        for (int i = 1; i <= nrLines; ++i)
            element[i][nr] = -element[i][nr],
            sumColumn[nr] += element[i][nr];
    }
}

int matrixSum() {
    int returnable = 0;
    for (int i = 1; i <= nrLines; ++i)
        for (int j = 1; j <= nrColumns; ++j)
            returnable += element[i][j];
    return returnable;
}

void backTrackColumns(int nowColumn) {
    if (nowColumn == nrColumns) {
        maxSum = max(maxSum, matrixSum());
        flip(1, nowColumn);
        maxSum = max(maxSum, matrixSum());
        flip(1, nowColumn);
    }
    else {
        backTrackColumns(nowColumn + 1);
        flip(1, nowColumn);
        backTrackColumns(nowColumn + 1);
        flip(1, nowColumn);
    }
}

void backTrackLines(int nowLine) {
    if (nowLine == nrLines) {
        maxSum = max(maxSum, matrixSum());
        backTrackColumns(1);
        flip(0, nowLine);
        maxSum = max(maxSum, matrixSum());
        backTrackColumns(1);
        flip(0, nowLine);
    }
    else {
        backTrackLines(nowLine + 1);
        flip(0, nowLine);
        backTrackLines(nowLine + 1);
        flip(0, nowLine);
    }
}

int main()
{
    fin >> nrLines >> nrColumns;
    for (int i = 1; i <= nrLines; ++i) {
        for (int j = 1; j <= nrColumns; ++j) {
            fin >> element[i][j];
            sumLine[i] += element[i][j];
            sumColumn[j] += element[i][j];
        }
    }
    backTrackLines(1);
    fout << maxSum;
    return 0;
}