Pagini recente » Cod sursa (job #1317368) | Cod sursa (job #1629670) | Cod sursa (job #2196196) | Cod sursa (job #1353299) | Cod sursa (job #3200430)
#include <fstream>
#include <cmath>
#define maxim 17
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int mat[maxim][maxim], stack[maxim], level, n, m, smax=0;
void citire() {
fin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
fin >> mat[i][j];
}
int valid() {
return (level <= n);
}
int solutie() {
return (level == n);
}
void flip() {
for (int i = 1; i <= n; i++)
if (stack[i]) {
for (int j = 1; j <= m; j++)
mat[i][j] = mat[i][j] * (-1);
}
int smat = 0, s;
for (int j = 1; j <= m; j++) {
s = 0;
for (int i = 1; i <= n; i++)
s += mat[i][j];
s = max(s, s*(-1));
smat += s;
}
if (smat > smax)
smax = smat;
for (int i = 1; i <= n; i++)
if (stack[i]) {
for (int j = 1; j<= m; j++)
mat[i][j] = mat[i][j] * (-1);
}
}
void bkt() {
if (valid()) {
for (int i = 0; i <= 1; i++) {
stack[level] = i;
if (solutie())
flip();
level++;
bkt();
level--;
}
}
}
int main() {
citire();
bkt();
fout << smax;
return 0;
}