Pagini recente » Cod sursa (job #293847) | Cod sursa (job #2361591) | Cod sursa (job #1755238) | Profil crisanina | Cod sursa (job #685874)
Cod sursa(job #685874)
#include<iostream>
#include<fstream>
using namespace std;
ifstream f;
ofstream g;
int n,k,st[20],i,j,v,m,S,s,maxim=0;
int a[16][16];
int x,y;
int sl(int a[16][16], int I) // sl - schimba linia || nl - numarul liniei || op . inmultire cu 1 sau -1
{
int J;
for(J=1;J<=m;J++)
a[I][J]=-a[I][J];
}
int vsuma(int a[16][16])
{
s=0; S=0;
int I,J;
for(I=1;I<=m;I++)
{
for(J=1;J<=n;J++)
{ s=s+a[I][J];
}
S=S+s;
}
return S;
}
void citire()
{
f.open("flip.in");
f>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>a[i][j];
}
// back
void init()
{
k=1;
st[k]=0;
}
void valid(int &v, int k)
{
v=1;
}
int succesor()
{
if(st[k]<=x) return 1;
return 0;
}
int solutie()
{
if(k==x) return 1;
return 0;
}
void tipar()
{ // S compari cu maxim
//
for(i=1;i<=x;i++)
{
if(st[i]==2)
{
sl(a,i);
if(maxim<vsuma(a)) maxim=vsuma(a);
sl(a,i); // undo - o face la loc
}
}
}
void bkt()
{
init();
while(k>0)
{
v=0;
while( !v && st[k]<y)
{
st[k]++;
valid(v,k);
}
if(!v)k--;
else if(solutie()) tipar();
else
{
k++;
st[k]=0;
}
} // de la while
}
int main()
{
citire();
x=n;
y=2;
bkt();
// bkt(m,2);
g.open("flip.out");
g<<maxim+1;
}