Pagini recente » Cod sursa (job #2541692) | Cod sursa (job #2586185) | Cod sursa (job #1397664) | Cod sursa (job #1676198) | Cod sursa (job #2046412)
#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;
}