Cod sursa(job #1460769)

Utilizator om6gaLungu Adrian om6ga Data 13 iulie 2015 20:47:46
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

FILE *in,*out;
int m, n, i, j, k, aux;
int a[18][18], b[18][18], s_line[18], aux_line[18];
long long sum, sum_aux;


void prep_data() //transpunere 'a' 
{
    if (m > n)
    {
        for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            b[j][i] = a[i][j];
            a[i][j] = 0;
        }
        aux = m;
        m = n;
        n = aux;
        for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            a[i][j] = b[i][j];
    }
}

 
int main()
{
    in=fopen("flip.in","r");
    out=fopen("flip.out","w");
    fscanf(in,"%d %d",&n,&m); 

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) 
            fscanf(in,"%d",&a[i][j]);

    prep_data(); //in caz ca-i nevoie de transpunere; backtrack dupa dimensiunea mai mica dintre m si n


    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++) 
        {
            s_line[i] += a[i][j];
            sum += a[i][j];
        }
    }

    for (k = 1; k < (1 << m); k++)
    {
        sum_aux = 0;
        memcpy(aux_line, s_line, 18*sizeof(int));

        for (j = 1; j <= m; j++)
        {
            if ((1 << (j-1)) & k) //flip coloana j
            {
                for (i = 1; i <= n; i++)
                {
                    aux_line[i] -= (2*a[i][j]); //diferenta intre + a[i][j] si - a[i][j] este de 2*a[i][j]
                }
            }
        }
        for (i = 1; i <= n; i++)
        {        
            if (aux_line[i] < 0)
            {
                aux_line[i] *= -1; //flip linia i
            }
            sum_aux += aux_line[i];
        }
        if (sum_aux > sum)
            sum = sum_aux;
    }

    
    fprintf(out,"%lld",sum);
    fclose(in);
    fclose(out);
    return 0;
}