Cod sursa(job #2047517)

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

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

bool lineFlipped[20], columnFlipped[20];

vector < int > nrWhereFlip;

inline int matrixSum() {
    int returnable = 0;
    for (int i = 1; i <= nrLines; ++i)
        for (int j = 1; j <= nrColumns; ++j) {
            if (lineFlipped[i] and columnFlipped[j]) {
                returnable += element[i][j];
                continue;
            }
            if (lineFlipped[i]) {
                returnable += -element[i][j];
                continue;
            }
            if (columnFlipped[j]) {
                returnable += -element[i][j];
                continue;
            }
            returnable += element[i][j];
        }
    return returnable;
}

void doForColumns() {
    for (int i = 1; i <= nrColumns; ++i) {
        int sumHere = 0;
        for (int j = 1; j <= nrLines; ++j)
            if (lineFlipped[j])
                sumHere += -element[j][i];
            else
                sumHere += element[j][i];
        if (sumHere < 0)
            columnFlipped[i] = true,
            nrWhereFlip.push_back(i);
    }
}

void undoForColumns() {
    for (int i = 0; i < nrWhereFlip.size(); ++i)
        columnFlipped[nrWhereFlip[i]] = false;
    nrWhereFlip.clear();
}

void backTrackLines(int nowLine) {
    if (nowLine == nrLines) {
        doForColumns();
        maxSum = max(maxSum, matrixSum());
        undoForColumns();
        lineFlipped[nowLine] = true;
        doForColumns();
        maxSum = max(maxSum, matrixSum());
        undoForColumns();
        lineFlipped[nowLine] = false;
    }
    else {
        backTrackLines(nowLine + 1);
        lineFlipped[nowLine] = true;
        backTrackLines(nowLine + 1);
        lineFlipped[nowLine] = false;
    }
}

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