Pagini recente » Cod sursa (job #1329031) | Cod sursa (job #2350465) | Cod sursa (job #1840074) | Cod sursa (job #1839871) | Cod sursa (job #2334649)
#include <iostream>
#include <climits>
#include <vector>
#include <fstream>
#include <cmath>
using namespace std;
int sum(vector<vector<int> > a)
{
int s = 0;
for (int i = 0; i < a.size(); i++)
{
for (int j = 0; j < a[i].size(); j++)
s += a[i][j];
}
return s;
}
void input(vector <vector<int> > &table, int &n, int &m)
{
ifstream f("flip.in");
f >> n >> m;
for (int i = 0; i < n; i++)
{
table.resize(table.size()+1);
for (int j = 0; j < m; j++)
{
int temp;
f >> temp;
table[i].push_back(temp);
}
}
f.close();
}
void flipRow(vector<vector<int> > &a, int x, int m)
{
for (int i = 0; i < m; i++)
a[x][i] = -a[x][i];
}
void flipCol(vector<vector<int> > &a, int y, int n)
{
for (int i = 0; i < n; i++)
a[i][y] = -a[i][y];
}
void maxSum(vector<vector<int> > a, vector<vector<bool> > neg, int n, int m, int &temp_sum)
{
for (int x = 0; x < n; x++)
if (neg[0][x] == 1)
flipRow(a, x, m);
for (int y = 0; y < m; y++)
if (neg[1][y] == 1)
flipCol(a, y, n);
if (sum(a) > temp_sum)
temp_sum = sum(a);
}
int seek_sums(vector<vector<int> > &a, int n, int m)
{
int Sum = INT_MIN;
vector<vector<bool> > neg(2);
neg[0].resize(n);
for (int i = 0; i < n; i++)
neg[0][i] = 0;
neg[1].resize(m);
int rowMax = pow(2, n);
int colMax = pow(2, m);
for (int row = 0; row < rowMax; row++)
{
for (int j = m-1; j >= 0; j--)
neg[1][j] = 0;
for (int col = 0; col < colMax; col++)
{
maxSum(a, neg, n, m, Sum);
int j = m-1;
while (neg[1][j] == 1)
{
neg[1][j] = 0;
if (j > 0)
j--;
}
neg[1][j] = 1;
}
int i = n-1;
while (neg[0][i] == 1 && i >= 0)
{
neg[0][i] = 0;
if (i > 0)
i--;
}
neg[0][i] = 1;
}
return Sum;
}
int main()
{
vector<vector<int> >table;
ofstream g("flip.out");
int n, m;
input(table, n, m);
g << seek_sums(table, n, m);
g.close();
return 0;
}