Cod sursa(job #864156)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 24 ianuarie 2013 18:27:48
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>

using namespace std;

//Maximul global si semnele liniilor; in v se tine matricea, iar n si m sunt dimensiunile acesteia 
int maxim,minus_linie[16];
int v[16][16];
int n,m;

void coloane()
{
	//Suma calculeaza maximul posibil pentru liniile alese iar curent este suma pe coloana pe care lucram, i, j contoare
	int suma=0,curent=0,i,j;
	
	//Pentru fiecare coloana
	for(j=0;j<m;j++)
	{	
		//Suma de pe coloana curenta este initial 0
		curent=0;
		
		//Pentru fiecare linie
		for(i=0;i<n;i++)
			curent+=(minus_linie[i]*v[i][j]); //curent creste cu valoare de la v[i][j], cu semn
			
		//Evident, maximul va fi modulul sumei coloanei curente
		if(curent<0)
			curent*=(-1);
		suma+=curent;
	}
	
	//Solutia din configuratia de linii poate fi globala sau nu
	if(suma>maxim)
		maxim=suma;
}

//Backtracking pe linii
void back_linie(int poz)
{
	//Daca s-a ajuns la sfarsitul alegerii liniilor, atunci determinam in O(n*m)
	//cea mai buna alegere pentru coloane
    if(poz==n)
	{
		coloane();
		return;
	}
	
	//Incercam cu +
	back_linie(poz+1);
		
	//Incercam si cu -
	minus_linie[poz]=-1;
	back_linie(poz+1);
	minus_linie[poz]=1;
}


int main()
{
	//Deschiderea fisierelor de intrare si iesire
	ifstream fin("flip.in");
	ofstream fout("flip.out");

	//Maximul este initial foarte mic (mai mic decat minimul impus de datele problemei) 
	maxim=-256000005;
	
	//Declararea a doua variabile contor
	int i,j;
	
	//Citirea dimensiunilor tabloului
	fin>>n;
	fin>>m;
	
	//Citim matricea si initalizam semenle cu + (adica 1)
	for(i=0;i<n;i++)
	{
		minus_linie[i]=1;
		
		for(j=0;j<m;j++)
			fin>>v[i][j];
	}
	
	//Facem backtracking pe semnele de la linii
	back_linie(0);
	
	//Afisam maximul
	fout<<maxim<<'\n';
	
	//Inchidem fisierele de intrare si iesire
	fin.close();
	fout.close();
	return 0;
}