Pagini recente » Cod sursa (job #339610) | Cod sursa (job #342025) | Cod sursa (job #845753) | Cod sursa (job #2097836) | Cod sursa (job #24935)
Cod sursa(job #24935)
#include<stdio.h>
int st[100],n,m,a[17][17],b[17][17],smax,k,as,ev;
void citire()
{
int i,j;
FILE * in = fopen("flip.in","r");
fscanf(in,"%d %d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fscanf(in,"%d",&a[i][j]);
fclose(in);
}
void init()
{
st[k]=0;
}
int succesor()
{
if(st[k]<n)
{
++st[k];
return 1;
}
return 0;
}
int solutie()
{
return 1;
}
void tipar()
{
FILE * out = fopen("flip.out","w");
fprintf(out,"%d",smax);
}
int validare()
{
int i,j,s0,stotal;
if(k>n) return 0;
for(i=1;i<k;i++)
if(st[k]==st[i]) return 0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
b[i][j]=a[i][j];
for(i=1;i<=k;i++)
{
for(j=1;j<=m;j++)
b[st[i]][j] *= (-1);
}
stotal = 0;
for(i=1;i<=m;i++)
{
s0 = 0;
for(j=1;j<=n;j++)
{
s0 += b[j][i];
}
if(s0<0) s0 *= (-1);
stotal += s0;
}
if(stotal>smax) smax = stotal;
return 1;
}
void bkt()
{
k=1;
init();
while(k)
{
do
{
as=succesor();
if(as) ev=validare();
}while(as&&!ev);
if(as)
if(solutie());
else
{
++k;
init();
}
else k--;
}
}
int main()
{
citire();
bkt();
tipar();
return 0;
}