Pagini recente » Cod sursa (job #3220547) | Cod sursa (job #236931) | Cod sursa (job #3121519) | Cod sursa (job #1066848) | Cod sursa (job #1225765)
#include <stdio.h>
#include <iostream>
#include <limits.h>
#include <fstream>
using namespace std;
int** matrix;
int solution;
int* switcher;
void verify(int n,int m)
{
int S = 0;
for (int i = 0; i < n ; i++)
{
int s = 0;
for (int j = 0; j < m; j++)
{
if (switcher[j]) s += matrix[i][j];
else s -= matrix[i][j];
}
if (s < 0) S -= s;
else S += s;
}
if (S > solution) solution = S;
}
//backtrack
void FindMax(int k,int n,int m)
{
if (k == m)
{
verify(n,m);
}
else
{
switcher[k] = 0;
FindMax(k + 1,n,m);
switcher[k] = 1;
FindMax(k + 1, n, m);
}
}
void Flip(int n,int m)
{
solution = INT_MIN;
FindMax(0, n, m);
}
int main()
{
int n, m;
ifstream reader;
reader.open("flip.in");
reader >> n >> m;
matrix = new int*[n];
for (int i = 0; i < n; ++i)
matrix[i] = new int[m];
switcher = new int[m];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
reader >> matrix[i][j];
}
reader.close();
Flip(n, m);
ofstream writter;
writter.open("flip.out");
writter << solution;
writter.close();
return 0;
}