Pagini recente » Cod sursa (job #1040750) | Cod sursa (job #869942) | Cod sursa (job #1614368) | Cod sursa (job #1004415) | Cod sursa (job #102146)
Cod sursa(job #102146)
#include<iostream.h>
#include<fstream.h>
typedef int stiva[100];
int n,k,ev,as,suma=0,a[16][16],N,M,b[16][16];
stiva st;
void citire()
{int i,j;
fstream fin("flip.in",ios::in);
fin>>N;
fin>>M;
for(i=1;i<=N;i++)
for(j=1;j<=M;j++) fin>>a[i][j];
fin.close();
}
void reset()
{
int i,j;
for(i=1;i<=N;i++)
for(j=1;j<=M;j++) b[i][j]=a[i][j];
}
void greedy()
{int i,j,s;
if(M<N)
{
for(i=1;i<=N;i++)
{s=0;
for(j=1;j<=M;j++)s+=b[i][j];
if(s<0)
{
for(j=1;j<=M;j++) b[i][j]*=-1;
}
}
}
else
{
for(i=1;i<=M;i++)
{s=0;
for(j=1;j<=N;j++)s+=b[j][i];
if(s<0)
{
for(j=1;j<=N;j++) b[j][i]*=-1;
}
}
}
}
void flip()
{int i,j,s=0;
reset();
if(M<N)
{
for(i=1;i<=N;i++)
for(j=1;j<=M;j++)if(st[j]==1) b[i][j]*=-1;
}
else
{
for(i=1;i<=M;i++)
for(j=1;j<=N;j++)if(st[j]==1) b[j][i]*=-1;
}
for(i=1;i<=N;i++)
for(j=1;j<=M;j++) s+=b[i][j];
if(s>suma) suma=s;
greedy();
s=0;
for(i=1;i<=N;i++)
for(j=1;j<=M;j++) s+=b[i][j];
if(s>suma) suma=s;
}
void init()
{
st[k]=-1;
}
int succesor()
{
if(st[k]<1)
{st[k]=st[k]+1; return 1;}
else return 0;
}
int valid()
{
return 1;
}
int solutie()
{
return k==n;
}
void tipar()
{
flip();
}
void bt()
{
k=1;
init();
while(k>0)
{
as=1;ev=0;
while(as && !ev)
{
as=succesor();
if(as) ev=valid();
}
if(as)
if(solutie())tipar();
else {k++;init();}
else k--;
}
}
void scrie()
{
fstream fout("flip.out",ios::out);
fout<<suma;
fout.close();
}
int main()
{
citire();
if(N<M)n=N;
else n=M;
bt();
scrie();
}