Cod sursa(job #2046840)

Utilizator nelsonmondialuAwala pa barosaneala nelsonmondialu Data 24 octombrie 2017 10:05:45
Problema Jocul Flip Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");

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

vector < int > nrWhereFlip;

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

inline void doForColumns() {
    for (int i = 1; i <= nrColumns; ++i)
        if (sumColumn[i] < 0) {
            flip(1, i);
            nrWhereFlip.push_back(i);
        }
}

inline void undoForColumns() {
    for (int i = 0; i < nrWhereFlip.size(); ++i)
        flip(1, nrWhereFlip[i]);
    nrWhereFlip.clear();
}

void backTrackLines(int nowLine) {
    if (nowLine == nrLines) {
        doForColumns();
        maxSum = max(maxSum, sumHere);
        undoForColumns();
        flip(0, nowLine);
        doForColumns();
        maxSum = max(maxSum, sumHere);
        undoForColumns();
        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];
            sumHere += element[i][j];
            sumLine[i] += element[i][j];
            sumColumn[j] += element[i][j];
        }
    }
    backTrackLines(1);
    fout << maxSum;
    return 0;
}