Cod sursa(job #480592)

Utilizator ariel_roAriel Chelsau ariel_ro Data 28 august 2010 19:51:26
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <limits.h>
#include <math.h>
#include <stdlib.h>

using namespace std;

ifstream f("flip.in");
ofstream g("flip.out");

int matr[16][16], n, m, sum, maxim;
bool minMask[65536];

void calcSumLin(int cols[16])
{
    for (int i = 0; i < n; i++)
    {
        int sumLin = 0;
        for (int j = 0; j < m; j++)
            sumLin += matr[i][j] * cols[j];

        sum += (sumLin < 0) ? -sumLin : sumLin;
    }
    if (sum > maxim)
        maxim = sum;
}

void calcSum(bool mask[], int k)
{
    sum = 0;
    int cols[k];
	for (int j = 0; j < k; j++)
	{
        if (mask[j] == true)
		    cols[j] = -1;
        else
            cols[j] = 1;
	}

    calcSumLin(cols);
}

int next(bool mask[], int n) {
	int i;
	for (i = 0; (i < n) && mask[i]; ++i)
		mask[i] = false;

	if (i < n) {
		mask[i] = true;
		return 1;
	}
	return 0;
}

int main() {
	maxim = INT_MIN;

    for (int i = 0; i < 65536; i++)
            minMask[i] = false;

	f>>n>>m;
	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++)
        f>>matr[i][j];

	bool mask[65536];
	int i;
	for (i = 0; i < m; ++i)
		mask[i] = false;

	// 2 ^ m posibilitati
	calcSum(mask, m);

	/* Print all the others */
	while (next(mask, m))
		calcSum(mask, m);

    cout<<maxim<<endl;
    g<<maxim;
	return 0;
}