Cod sursa(job #546774)

Utilizator BigDaddyDDaniel Alexandru Radu BigDaddyD Data 5 martie 2011 14:57:52
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
//declaratii
#include<fstream>
using namespace std;
fstream f("flip.in", ios::in),
		g("flip.out", ios::out);
int smax, i, j, sl[17], x[17], n, m, a[18][18];
//sl -> suma liniei
//a -> matricea in care sunt valorile
//n -> numarul de linii
//m -> numarul de coloane
//x -> stiva

void init(int k)
{
	x[k]=-1; //intializarea elementului din stiva cu numarul de ordine k la valoarea -1
}
int succ(int k)
{
	if(k<=m && x[k]<1)
	{
		x[k]++;
		return 1;
	}
	return 0;
}
int valid(int k)
{
	return 1;
}
int solutie(int k)
{
	if(k==m)
		return 1;
	return 0;
}
void tipar(int k)
{
	int i, s, c;
	s=0;
	for(i=1; i<=n; ++i)
	{
		c=sl[i]; //c primeste suma liniei cu numarul de ordine i
		for(j=1; j<=m; ++j)
			if(x[j]==1)
				c=c+2*(-a[i][j]);
		if(c<-c)
			s=s+(-c);
		else
			s+=c;
	}
	
	if(s>smax)
		smax=s;
}
void back() //functia back() implementeaza algoritmul backtracking sub forma iterativa
{
	int i, k; //k -> nivelul stivei
	k=1; //nivelul stivei este initializat la 1
	init(k);
	while(k>0) //cat timp nu s-au epuizat toate solutiile
	{
		i=0;
		while(i==0 && succ(k))
			if(valid(k)) //orice varianta e valida
				i=1;
		if(i==1)
		{
			if(solutie(k)) //daca varianta actuala reprezinta o solutie
				tipar(k); //se afiseaza
			else
			{
				k++; //altfel se trece la urmatorul nivel al stivei
				init(k); //se initalizeaza elementul din stiva cu numarul de ordine k
			}
		}
		else
			k--; //
	}
}
int main() //functia main() 
{
	//are implementata si functia citire()
	f>>n>>m;
	for(i=1; i<=n; ++i)
	{
		for(j=1; j<=m; ++j)
		{
			f>>a[i][j];
			sl[i]+=a[i][j];
		}
	}
	back();
	g<<smax;
	
}