Pagini recente » Cod sursa (job #2524548) | Cod sursa (job #426488) | Cod sursa (job #119906) | Cod sursa (job #573238) | Cod sursa (job #546774)
Cod sursa(job #546774)
//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;
}