Pagini recente » Cod sursa (job #1156264) | Cod sursa (job #279119) | Cod sursa (job #2439577) | Cod sursa (job #1280275) | Cod sursa (job #1807994)
#include <iostream>
#include <fstream>
using namespace std;
int N, M;
int mx;
int mat[17][17];
void flip(int x, int y)
{
if(x == 1)
{
for(int a = 0; a < M; a++)
{
mat[y][a] = mat[y][a] * (-1);
}
}
else
{
for(int a = 0; a < N; a++)
{
mat[a][y] = mat[a][y] * (-1);
}
}
}
int sum()
{
int s = 0;
for(int a = 0; a < N; a++)
{
for(int b = 0; b < M; b++)
{
s = s + mat[a][b];
}
}
return s;
}
int backtrack(int x)
{
if(x == N)
{
int k = sum();
if(k > mx)
mx = k;
}
else
{
flip(1, x);
backtrack(x + 1);
for(int a = 0; a < M; a++)
{
flip(2, a);
backtrack(x + 1);
}
flip(1, x);
backtrack(x + 1);
for(int a = 0; a < M; a++)
{
flip(2, a);
backtrack(x + 1);
}
}
}
int main()
{
ifstream i("flip.in");
ofstream o("flip.out");
i >> N >> M;
for(int a = 0; a < N; a++)
{
for(int b = 0; b < M; b++)
{
i >> mat[a][b];
}
}
backtrack(0);
o << mx;
return 0;
}