Pagini recente » Cod sursa (job #2009879) | Cod sursa (job #366483) | Cod sursa (job #354476) | Cod sursa (job #3193695) | Cod sursa (job #680970)
Cod sursa(job #680970)
#include<iostream>
#include<fstream>
using namespace std;
ifstream f;
ofstream g;
long a[16][16]; //fuchs optimizare * prima data sa mearga programul :)) !
int n,m,i,j;
int k,cc,maxim;
int st[90],stc[90];
void init(int s[90])
{
for(int i=1;i<=m;i++)
s[i]=0;
}
void afisare()
{
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
void comutal(int l)
{
int j;
for(j=1;j<=m;j++)
a[l][j]=-a[l][j];
}
void comutac(int c)
{
int i;
for(i=1;i<=n;i++)
a[i][c]=-a[i][c];
}
long sumal(int l)
{
long s=0;
int j;
for(j=1;j<=m;j++)
s=s+a[l][j];
return s;
}
long sumac(int c)
{
long s=0;
int i;
for(i=1;i<=n;i++)
s=s+a[i][c];
return s;
}
int sumat()
{
int csuma=0;
// afisare();
for(i=1;i<=n;i++)
{
csuma+=sumal(i);
}
return csuma;
}
//backtracking pt coloane
int solutiec(int k)
{
return(k==m+1);
}
void tiparc(int k)
{
for(int i=1;i<=m;i++)
{
// cout<<stc[i]<<" ";
if (stc[i]==2)
comutac(i);
if(maxim<sumat())
maxim=sumat();
}
// cout<<endl;
}
int validc(int k)
{
int ok=1;
/*for(int i=1;i<=k-1;i++)
if(st[k]==st[i])
ok=0;*/
return ok;
}
int succesorc(int k)
{
int ok=1;
if (stc[k]<2)
stc[k]++;
else
ok=0;
return ok;
}
void back2(int k)
{
if(solutiec(k))
tiparc(k);
else
while(succesorc(k))
{
if(validc(k))
{
stc[k+1]=0;
back2(k+1);
}
}
}
//backtracking pt linii
int solutie(int k)
{
return(k==n+1);
}
void tipar(int k)
{
for(int i=1;i<=n;i++)
{
// cout<<st[i]<<" ";
if (st[i]==2)
comutal(i);
if(maxim<sumat())
maxim=sumat();
init(stc);
back2(1);
}
// cout<<endl;
}
int valid(int k)
{
int ok=1;
/*for(int i=1;i<=k-1;i++)
if(st[k]==st[i])
ok=0;*/
return ok;
}
int succesor(int k)
{
int ok=1;
if (st[k]<2)
st[k]++;
else
ok=0;
return ok;
}
void back(int k)
{
if(solutie(k))
tipar(k);
else
while(succesor(k))
{
if(valid(k))
{
st[k+1]=0;
back(k+1);
}
}
}
int main()
{
long csuma=0;
// citirea //
f.open("flip.in");
f>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
f>>a[i][j];
}
}
// nu stiu daca am inteles ideea jocului
// sa speram ca e ce terbuie :)
// afisare();
maxim=0;
back(1);
cout<<endl;
//back2(1);
g.open("flip.out");
g<<maxim;
}