Cod sursa(job #1474175)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 21 august 2015 11:39:55
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;

const int maxSize = 16;

void subset(int k, int N, int M, int sum, int &maxSum, vector<int> st,
            int board[][maxSize])
{
    if (k == N + M + 1)
    {
        for (auto it : st)
        {
            it--;
            if (it < N)
            {
                for (int j = 0; j < M; j++)
                    sum -= board[it][j];
                for (int j = 0; j < M; j++)
                    sum += -board[it][j];
            }
            else
            {
                it -= N;
                for (int j = 0; j < N; j++)
                    sum -= board[j][it];
                for (int j = 0; j < N; j++)
                    sum += -board[j][it];
            }

            if (maxSum < sum)
                maxSum = sum;
        }
        return;
    }

    st.push_back(k);
    subset(k + 1, N, M, sum, maxSum, st, board);
    st.pop_back();
    subset(k + 1, N, M, sum, maxSum, st, board);
}

int main()
{
    int i, j, N, M;

    ifstream f("flip.in");
    f >> N >> M;
    int board[N][16];

    int sum = 0;
    for (i = 0; i < N; i++)
        for (j = 0; j < M; j++)
        {
            f >> board[i][j];
            sum += board[i][j];
        }
    f.close();

    vector<int> st;
    subset(1, N, M, sum, sum, st, board);

    ofstream g("flip.out");
    g << sum;
    g.close();
    return 0;
}