Cod sursa(job #480571)

Utilizator ariel_roAriel Chelsau ariel_ro Data 28 august 2010 17:35:52
Problema Jocul Flip Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 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];

int getSum(int matr[16][16])
{
    int s = 0;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        s += matr[i][j];

    return s;
}

template <class T>
void copyMatr(T m1[16][16], T m2[16][16], int n, int m)
{
    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        m1[i][j] = m2[i][j];
}

void calcSum(bool mask[], int k) {
    int cop[16][16];

    copyMatr<int>(cop, matr, 16, 16);

	for (int j = 0; j < k; j++)
	{
        if (mask[j])
		{
            for (int i = 0; i < n; i++)
                cop[i][j] *= -1;

            for (int i = 0; i < n; i++)
            {
                int sLin = 0;
                for (int k = 0; k < m; k++)
                    sLin += cop[i][k];

                if (sLin < 0)
                {
                    for (int l = 0; l < n; l++)
                        cop[i][l] *= -1;
                }

                sum = getSum(cop);
                if (sum > maxim)
                    maxim = sum;
            }
		}
	}
}

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<<endl;
	return 0;
}