Cod sursa(job #555168)

Utilizator RoCoderRo COder RoCoder Data 15 martie 2011 12:26:39
Problema Jocul Flip Scor 30
Compilator c Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <stdio.h>
//#include <string.h>
//fa combinatii de n luate cate k [0 la 16*2 -1]

int matrix[16][16];
int mat[16][16];
int v[32];
int n, m;
int maxim;

void max_matrix(int k)
{
    int i, j, s1=0;

    //memcpy(mat, matrix, sizeof(mat));

    for (i=0; i<n; i++)
        for (j=0; j<m; j++)
            mat[i][j]=matrix[i][j];

    for (i=0; i<k; i++)
        if(v[i]<=n)
        {
            for (j=0; j<m; j++)
                mat[v[i]-1][j]*=-1;
        }
        else
        {
            for (j=0; j<n; j++)
                mat[j][v[i]-n-1]*=-1;
        }

    for(i=0; i<n; i++)
        for(j=0; j<m; j++)
            s1+=mat[i][j];

    if(s1>maxim) maxim = s1;

}

void combinari(int n, int k, int i, int r)
{
    int j;

    if(i==k)
    {
        max_matrix(k);
        return;
    }

    for(j=r; j<=n; j++)
    {
        v[i]=j;
        combinari(n, k, i+1, j+1);
    }

}

void combinari2(n, k)
{
    int i, j, c, r=0;

        for (i=0; i<(1<<n); i++)
        {

            /* masking the j'th bit as j goes through all the bits,
             * count the number of 1 bits.  this is called finding
             * a population count.
             */
            for (j=0,c=0; j<32; j++) if (i & (1<<j)) c++;

            /* if that number is equal to k, print the combination... */

            if (c == k)
            {

                /* by again going through all the bits indices,
                 * printing only the ones with 1-bits
                 */

                for (j=0; j<32; j++) if (i & (1<<j)) v[r++]=j+1;//printf ("%d ", j+1);
                //printf ("\n");
                max_matrix(k);
                r=0;
            }
        }
}


int main ()
{
    int i, j;

    FILE *fi, *fo;
    fi=fopen("flip.in","r");
    fo=fopen("flip.out","w");

    fscanf(fi,"%d %d", &n, &m);

    for(i=0; i<n; i++)
        for(j=0; j<m; j++)
            fscanf(fi,"%d", &matrix[i][j]);

    //for(i=1; i<n+m; i++)
        //combinari(n+m, i, 0, 1);
    for(i=1; i<n+m; i++)
        combinari2(n+m, i);

    //printf("%d", maxim);
    fprintf(fo,"%d", maxim);

    //fclose(fi);
    fclose(fo);
}