Pagini recente » Cod sursa (job #2877830) | Cod sursa (job #3288192) | Cod sursa (job #338002) | Cod sursa (job #995076) | Cod sursa (job #1870768)
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,v[17][17],x[17],copiev[17][17],maxim=-999999;
FILE *intrare,*iesire;
void backtracking(int pos)
{
int i,j,suma=0,k,sumamatrice=0;
bool y=false;
if (pos==n)
{
for (i=0; i<=n-1; ++i)
{
if (x[i]==1)
{
//inmultesc cu -1 LINIA marcata cu 1
for (j=0; j<=m-1; ++j)
{
v[i][j]=-1*v[i][j];
}
}
}
//dupa ce am inmultit cu -1 liniile din submultime, verific daca exista coloane negative sau nu,iar daca exista o inmultesc cu -1
for (k=0; k<=m-1; ++k)
{
for (j=0; j<=n-1; ++j)
{
suma=suma+v[j][k];
}
if (suma<0)
{
for (j=0; j<=n-1; ++j)
{
v[j][k]=-1*v[j][k];
}
}
suma=0;
}
//fac suma matricii
for (i=0; i<=n-1; ++i)
{
for (j=0; j<=m-1; ++j)
{
sumamatrice=sumamatrice+v[i][j];
}
}
//aflu suma maxima si o afisez
if (sumamatrice>maxim)
{
maxim=sumamatrice;
}
for (i=0; i<=n-1; ++i)
{
if (x[i]==1)
y=true;
else
{
y=false;
break;
}
}
if (y==true)
fprintf(iesire,"%d",maxim);
//reset-uri
for (i=0; i<=n-1; ++i)
{
for (j=0; j<=m-1; ++j)
{
v[i][j]=copiev[i][j];
}
}
sumamatrice=0;
}
else
{
for (i=0; i<=1; ++i)
{
x[pos]=i;
backtracking (pos+1);
}
}
}
int main()
{
int i,j;
intrare=fopen("flip.in","r");
iesire=fopen("flip.out","w");
fscanf(intrare,"%d%d",&n,&m);
for (i=0; i<=n-1; ++i)
{
for (j=0; j<=m-1; ++j)
{
fscanf(intrare,"%d",&v[i][j]);
copiev[i][j]=v[i][j];
}
}
backtracking(0);
}