Cod sursa(job #1200573)

Utilizator ValyGabrielMitrea Valentin Gabriel ValyGabriel Data 22 iunie 2014 21:35:04
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>

using namespace std;


int pow(int nr, int p)
{
    int result;
        
    if (p == 0)
        result = 1;
    else if (p == 1)
        result = nr;
    else {
        result = pow(nr, p/2);
        	
        if (p % 2 == 0)
        	result *= result;
        else
        	result = result * result * nr;	
    }

    return result;
}


int sumaMatrice(int n, int m, int matrix[16][16])
{
	int suma = 0;

	for (int i = 0; i < n; i ++)
		for (int j = 0; j < m; j ++)
			suma += matrix[i][j];

	return suma;
}


void incrementVector(char *vector, int length)
{
	for (int i = length - 1; i >= 0; i --)
		if (vector[i] == 0)
		{
			vector[i] ++;
			for (int j = i + 1; j < length; j ++)
				vector[j] = 0;

			break;
		}
}


int joculFlip(int n, int m, int matrix[16][16])
{
	int suma, aux, length = n + m, nrSubmultimi = pow(2, length);
	char *vector = (char*)calloc(n + m, sizeof(char));


	suma = sumaMatrice(n, m, matrix);

	for (int i = 1; i <= nrSubmultimi; i ++)
	{
		incrementVector(vector, length);

		for (int j = 0; j < length; j ++)
			if (vector[j] == 1)
				if (j < n)
					for (int k = 0; k < m; k ++)
						matrix[j][k] = -matrix[j][k];
				else
					for (int k = 0; k < n; k ++)
						matrix[k][j - n] = -matrix[k][j - n];

		aux = sumaMatrice(n, m, matrix);
		if (aux > suma)
			suma = aux;

		for (int j = 0; j < length; j ++)
			if (vector[j] == 1)
				if (j < n)
					for (int k = 0; k < m; k ++)
						matrix[j][k] = -matrix[j][k];
				else
					for (int k = 0; k < n; k ++)
						matrix[k][j - n] = -matrix[k][j - n];

	}

	free(vector);


	return suma;
}


int main(int argc, char** argv)
{
    int n, m, matrix[16][16];
    
    ifstream in("flip.in");
    ofstream out("flip.out");
    
    in >> n;
	in >> m;

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

    out << joculFlip(n, m, matrix);


    in.close();
	out.close();
    
    return 0;
}