Cod sursa(job #832756)

Utilizator adrian.harabulaAdrian Harabula adrian.harabula Data 11 decembrie 2012 12:58:46
Problema Jocul Flip Scor 40
Compilator c Status done
Runda Arhiva de probleme Marime 2.96 kb
#include <stdio.h>
#include <math.h>
#include <limits.h>
#define MAXN 16
#define MAXM 16

int n, m, sum = INT_MIN;
int lineflip[MAXN] = {0};
int colflip[MAXM] = {0};

int a[MAXN][MAXM], backup[MAXN][MAXM];

// save a backup for a matrix
void copy()
{
    int i, j;
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            backup[i][j] = a[i][j];
    
}

// restore a matrix to original state
void copy_r()
{
    int i, j;
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            a[i][j] = backup[i][j];
    
}

// binary addition for flip vectors
void binary_add(int *flip, int n)
{
    n -= 1;
    while (1)
    {
        flip[n] += 1;
        flip[n] %= 2;
        if (flip[n] == 0) n--;
            else
        break;
    }
}

// flip line
void mul_line(int i)
{
    int j;
    for (j = 0; j < m; j++)
        a[i][j] *= -1;
}

// flip col
void mul_col(int j)
{
    int i;
    for (i = 0; i < n; i++)
        a[i][j] *= -1;
}

// calculate current matrix sum
int matrix_sum()
{
    int i, j, sum = 0;
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            sum += a[i][j];
    return sum;
}

/**
  * print_matrix
  * used for debugging
  */
void print_matrix()
{
    int i, j;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < m; j++)
            printf("%d ", a[i][j]);
        printf("\n");
    }
}

/**
  * print_flip
  * used for debugging
  */
void print_flip(int *flip, int n)
{
    int i;
    for(i = 0; i < n; i++)
    {
            printf("%d", flip[i]);
    }
    //printf("\n");
}

int main()
{
    int i, j;

    freopen ("flip.in", "r", stdin);
    scanf("%d %d",&n ,&m);
    
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
    copy();
    
    /**
      * taking a very ugly approach here
      * this code generates ALL flip posibilities
      * and most of them repeats over and over again
      * 
      * this approach won't work for 100 points
      */
      
    for(i = 0; i < pow(2, n); i++)
    {
        /*
        print_flip(lineflip, n);
        printf("\n");
        */
        
        for(j = 0; j < pow(2, m); j++)
        {
            copy_r();
            
            // do the flips
            int k;
            for (k = 0; k < n; k++)
                if(lineflip[k]) mul_line(k);
            for (k = 0; k < m; k++)
                if(colflip[k]) mul_col(k);

            // search for max sum
            if(matrix_sum() > sum) sum = matrix_sum();
            
            /* used for debugging
            printf("%d ", matrix_sum());
            print_flip(colflip, m);
            printf("-");
            print_flip(lineflip, n);
            printf("\n");
            print_matrix();
            
            printf("      ");
            print_flip(colflip, m);
            printf("\n");
            */
            
            binary_add(colflip, m);
        }
        binary_add(lineflip, n);
    }
    
    freopen("flip.out", "w", stdout);
    printf("%d\n", sum);
    
    return 0;
}