Pagini recente » Cod sursa (job #2061688) | Cod sursa (job #1182528) | Cod sursa (job #2791904) | Cod sursa (job #1218224) | Cod sursa (job #1225585)
#include<iostream>
#include<fstream>
using namespace std;
//structura de date care retine o configuratie flip
struct permutatie
{//x - vectorul care retine coloanele inmultite cu -1
//y - vectorul care retine liniile inmultite cu -1
bool x[16],y[16];
};
//vectorul bool v[16] va retine o dimensiune unei configuratii flip
//nm va retine fie N, fie M
//subprogramul va modifica elementele vectorului, pentru a obtine urmatoarea combinare
void next ( int nm, bool v[16])
{
int i;
for(i=nm-1;i>=0;i--)
{
if(!v[i])
{v[i]=true;
int j,sf;
sf=1;
for(j=i-1;j>=0;j--)
{
if(v[j]){sf=0; j=-1;}
}
if(sf==1)
{
for(j=i+1;j<nm;j++)
v[j]=false;
}
i=-1;
}
}
}
//fuck yeah!
//subprogramul care returneaza suma unei anumite configuratii de tabla flip
int suma ( int n, int m,int flip[16][16], permutatie tabla)
{
int s=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if((tabla.x[i])==(tabla.y[j])) s=s+flip[i][j];
else s=s-flip[i][j];
}
cout<<"suma==="<<s<<endl;
return s;
}
//subprogramul care returneaza suma maxima
int sumamax( int n, int m, int flip[16][16])
{
//initializarea vectorilor bool
permutatie tabla;
for(int i=0;i<n;i++)
{
tabla.x[i]=false;
}
for(int i=0;i<m;i++)
{
tabla.y[i]=false;
}
int smax=suma(n,m,flip,tabla);
int sfarsitx=0;
int sfarsity=0;
//parcurgerea fiecarei combinatii
//parcurge combinarile coloanelor, apoi a liniilor pentru fiecare combinare a coloanelor.
while(!sfarsitx)
{
while(!sfarsity)
{
next(m,tabla.y);
int s=suma(n,m,flip,tabla);
if(smax<suma(n,m,flip,tabla))
smax=suma(n,m,flip,tabla);
sfarsity=1;
for(int xx=0;xx<m;xx++)
{
if(!tabla.y[xx])sfarsity=0;
}
}
sfarsitx=1;
for(int xx=0;xx<n;xx++)
{
if(!tabla.x[xx])sfarsitx=0;
}
next(n,tabla.x); sfarsity=0; for(int xx=0;xx<m;xx++)tabla.y[xx]=false;
}
return smax;
}
int main()
{
int n,m,flip[16][16];
ifstream f ("flip.in");
f>>n; f>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
f>>flip[i][j];
f.close();
ofstream g ("flip.out");
g<<sumamax(n,m,flip);
}