Cod sursa(job #2334649)

Utilizator Dan201399Frimu Daniel Dan201399 Data 2 februarie 2019 20:12:04
Problema Jocul Flip Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#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;
}