Pagini recente » Cod sursa (job #1609028) | Cod sursa (job #2470457) | Cod sursa (job #1773858) | Cod sursa (job #1003919) | Cod sursa (job #1225684)
#include <stdio.h>
#include <iostream>
#include <limits.h>
#include <fstream>
using namespace std;
int matrix[18][18];
int sum;
void FlipColumn(int i,int lines)
{
for (int j = 0; j < lines; j++)
{
sum -= 2 * matrix[j][i];
matrix[j][i] = -matrix[j][i];
}
}
void FlipLine(int j,int columns)
{
for (int i = 0; i < columns; i++)
{
sum -= 2 * matrix[j][i];
matrix[j][i] = -matrix[j][i];
}
}
int sum_matrix(int n, int m)
{
int sum = 0;
for (int i = 0; i < n;i++)
{
for (int j = 0; j < m; j++)
sum += matrix[i][j];
}
return sum;
}
//backtrack
int FindMax(int n,int m,int currentLine,int currentColumn)
{
int max = sum;
for (int i = currentLine; i < n; i++)
{
for (int j = currentColumn; j < m; j++)
{
int nextMax = FindMax(n, m, currentLine + 1, currentColumn);
if (max < nextMax) max = nextMax;
nextMax = FindMax(n, m, currentLine, currentColumn + 1);
if (max < nextMax) max = nextMax;
FlipLine(i,m);
nextMax = FindMax(n, m, currentLine + 1, currentColumn);
if (max < nextMax) max = nextMax;
FlipLine(i, m);
FlipColumn(j,n);
nextMax = FindMax(n, m, currentLine, currentColumn+1);
if (max < nextMax) max = nextMax;
FlipColumn(j, n);
}
}
return max;
}
int Flip(int n,int m)
{
int max = INT_MIN;
sum = sum_matrix(n, m);
max = FindMax(n, m, 0, 0);
return max;
}
int main()
{
int n, m;
ifstream reader;
reader.open("flip.in");
reader >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
reader >> matrix[i][j];
}
reader.close();
int max = Flip(n, m);
ofstream writter;
writter.open("flip.out");
writter << max;
writter.close();
return 0;
}