Cod sursa(job #832753)

Utilizator adrian.harabulaAdrian Harabula adrian.harabula Data 11 decembrie 2012 12:44:25
Problema Jocul Flip Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.37 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];

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

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

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

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

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

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;
}

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");
    }
}

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();
    
    for(i = 0; i < pow(2, n); i++)
    {

        
        /*
        print_flip(lineflip, n);
        printf("\n");
        */
        
        for(j = 0; j < pow(2, m); j++)
        {
            copy_r();
            int y;
            int x;
            for (x = 0; x < n; x++)
                if(lineflip[x]) mul_line(x);
            for (y = 0; y < m; y++)
                if(colflip[y]) mul_col(y);
            if(matrix_sum() > sum) sum = matrix_sum();
            /*
            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);
    }
    printf("%d\n", sum);
    
    return 0;
}