Cod sursa(job #300378)

Utilizator chibicitiberiuChibici Tiberiu chibicitiberiu Data 7 aprilie 2009 13:29:09
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.42 kb
#include<fstream>
#define sizelimit 18
using namespace std;

int array[sizelimit][sizelimit], mat[sizelimit][sizelimit];
int n, m, ii[sizelimit], jj[sizelimit];

/*********************************
 *      READ FROM FILE           *
 *********************************/
void read()
{
    ifstream in ("flip.in");
    in>>n>>m;
    for (int i=0;i<n;i++)
         for (int j=0;j<m;j++)
              in>>array[i][j];
    in.close();
}

/*********************************
 *     COPIE MATRICEA            *
 *********************************/
void copymat()
{
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            mat[i][j]=array[i][j];
}

/*********************************
 *     COMUTA                    *
 *********************************/
void comutalinia(int linia)
{
    for (int i=0;i<m;i++)
        mat[linia][i]*=-1;
}

void comutacoloana(int coloana)
{
    for (int i=0;i<n;i++)
        mat[i][coloana]*=-1;
}

/*********************************
 *     SUMA                      *
 *********************************/

long long suma()
{
    long long temp=0;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            temp+=mat[i][j];
    return temp;
}

/*********************************
 *     GENERATE, NEXT NUMBER     *
 *********************************/
void generatei(int len)
{
    for (int i=0;i<len;i++)
        ii[i+1]=i;
}

void generatej(int len)
{
    for (int i=0;i<len;i++)
        jj[i+1]=i;
}

bool nexti(int len)
{
    int i=len;
    bool cont=true;
    while (cont==true) {
        ii[i]++;

        if (ii[i]>=n) {
            ii[i]=0;
            i--;
            if (i==0) return false;
            continue;
        }
        i=len;
        cont=false;
        for (int j=1;j<=len && cont==false;j++)
            for (int k=1;k<j && cont==false;k++)
                if (ii[j]<=ii[k]) cont=true;

        if (i==0) return false;
    }

    return true;
}

bool nextj(int len)
{
    int i=len;
    bool cont=true;
    while (cont==true) {
        jj[i]++;

        if (jj[i]>=m) {
            jj[i]=0;
            i--;
            if (i==0) return false;
            continue;
        }
        i=len;
        cont=false;
        for (int j=1;j<=len && cont==false;j++)
            for (int k=1;k<j && cont==false;k++)
                if (jj[j]<=jj[k]) cont=true;

        if (i==0) return false;
    }

    return true;
}

/*********************************
 *     FIND BEST SOLUTIONS       *
 *********************************/
long long findsol()
{
    long long max=LLONG_MIN, sum;

    for (int nri=0;nri<=n;nri++)
        for (int nrj=0;nrj<=m;nrj++)
        {
            generatei(nri);
            generatej(nrj);
            /// trateaza cazuri speciale
            if (nri==0 && nrj==0) {
                copymat();
                sum=suma();
                if (sum>max) max=sum;
                continue;
            }
            else if (nri==0) {
                do {
                    copymat();
                    for (int j=1;j<=nrj;j++)
                        comutalinia(jj[j]);
                    sum=suma();
                    if (sum>max) max=sum;
                } while (nextj(nrj));
                continue;
            }

            else if (nrj==0) {
                do {
                    copymat();
                    for (int i=1;i<=nri;i++)
                        comutalinia(ii[i]);
                    sum=suma();
                    if (sum>max) max=sum;
                } while (nexti(nri));
                continue;
            }
            /// testeaza toate posibilitatile
            do {
                do {
                    copymat();
                    for (int i=1;i<=nri;i++)
                        comutalinia(ii[i]);
                    for (int j=1;j<=nrj;j++)
                        comutacoloana(jj[j]);
                    sum=suma();
                    if (sum>max) max=sum;
                } while (nextj(nrj));
            } while (nexti(nri));
        }

    return max;
}



/*********************************
 *        MAIN function          *
 *********************************/
int main()
{
    long long temp;
    /// read data from file
    read();

    /// find solutions
    temp=findsol();

    /// output solutions
    ofstream out ("flip.out");
    out<<temp;

    /// cleanup
    out.close();
    return 0;
}