Pagini recente » Cod sursa (job #2319183) | Cod sursa (job #2319680) | Cod sursa (job #2584278) | Cod sursa (job #3184092) | Cod sursa (job #2451014)
#include <iostream>
#include <fstream>
using namespace std;
int m[17][17], N, M;
ifstream fin("flip.in");
ofstream fout("flip.out");
long long s_max{-1800000000000};
//false: 1 | true: -1
void columns_backtracking(int column, bool state, int matrix[17][17])
{
if(state == true)
{
for(int k = 1; k <= N; k++) matrix[k][column] *= -1;
}
if(column == M)
{
long long s_current{0};
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
{
s_current += matrix[i][j];
}
}
s_max = max(s_max, s_current);
}
else {
columns_backtracking(column + 1, false, matrix);
columns_backtracking(column + 1, true, matrix);
}
}
//false: 1 | true: -1
void line_backtracking(int line, bool state, int matrix[17][17])
{
if(state == true)
{
for(int k = 1; k <= M; k++) matrix[line][k] *= -1;
}
if(line == N)
{
columns_backtracking(1, false, matrix);
columns_backtracking(1, true, matrix);
}
else
{
line_backtracking(line + 1, false, matrix);
line_backtracking(line + 1, true, matrix);
}
}
int main()
{
fin >> N >> M;
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
{
fin >> m[i][j];
}
}
line_backtracking(1, false, m);
line_backtracking(1, true, m);
fout << s_max;
}