Cod sursa(job #1225585)

Utilizator blackdragonflyTeodor P blackdragonfly Data 2 septembrie 2014 23:06:48
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#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);

}