Pagini recente » Cod sursa (job #667459) | Cod sursa (job #2290839) | Rating ana are mere (anaaremere112358) | Cod sursa (job #1892442) | Cod sursa (job #2047517)
#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;
}