Pagini recente » Cod sursa (job #235098) | Cod sursa (job #572570) | Cod sursa (job #2203460) | Cod sursa (job #2451854) | Cod sursa (job #2451009)
#include <iostream>
#include <fstream>
using namespace std;
int matrix[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)
{
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);
columns_backtracking(column + 1, true);
}
//removing the change
if(state == true)
{
for(int k = 1; k <= N; k++) matrix[k][column] *= -1;
}
}
//false: 1 | true: -1
void line_backtracking(int line, bool state)
{
if(state == true)
{
for(int k = 1; k <= M; k++) matrix[line][k] *= -1;
}
if(line == N)
{
columns_backtracking(1, false);
columns_backtracking(1, true);
}
else
{
line_backtracking(line + 1, false);
line_backtracking(line + 1, true);
}
//removing the change
if(state == true)
{
for(int k = 1; k <= M; k++) matrix[line][k] *= -1;
}
}
int main()
{
fin >> N >> M;
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
{
fin >> matrix[i][j];
}
}
line_backtracking(1, false);
line_backtracking(1, true);
fout << s_max;
}