Cod sursa(job #1481346)

Utilizator amneCornel Cruceru amne Data 4 septembrie 2015 11:31:38
Problema Jocul Flip Scor 30
Compilator c Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <stdio.h>
#include <stdlib.h>

int bitmasks[16] = {
 1 << 1,
 1 << 2,
 1 << 3,
 1 << 4,
 1 << 5,
 1 << 6,
 1 << 7,
 1 << 8,
 1 << 9,
 1 << 10,
 1 << 11,
 1 << 12,
 1 << 13,
 1 << 14,
 1 << 15,
 1 << 16
};

int current_line_mask = 0, current_column_mask = 0;

int sum_matrix(int n, int m,  int flip[n][m]){
    int sum = 0, i ,j;
    for(i=0;i<n;i++){
	for(j=0;j<m;j++){
	    sum += flip[i][j];
	}
    }
    return sum;
}

int sum_line(int n, int m, int flip[n][m], int l){
    int sum = 0, i;
    for(i = 0;i<m;i++){
	sum += flip[l][i];
    }
    return sum;
}

int sum_column(int n, int m, int flip[n][m], int c){
    int sum = 0, i;
    for(i = 0;i<n;i++){
	sum += flip[i][c];
    }
    return sum;
}



void flip_matrix_line(int n, int m, int flip[n][m], int l){
    int j;
    for(j=0;j<m;j++){
	flip[l][j] *= -1;
    }
}

void flip_matrix_column(int n, int m, int flip[n][m], int c){
    int i;
    for(i=0;i<n;i++){
	flip[i][c] *= -1;
    }
}

void show_matrix(int n, int m, int flip[n][m]){

    int i,j;
    for(i=0;i<n;i++){
	for(j=0;j<m;j++){
	    printf("%d ",flip[i][j]);
	}
	printf("\n");
    }

}

void flip_matrix_by_mask(int n, int m, int flip[n][m], int sum_lines[n], int sum_columns[m], int line_mask, int column_mask){
    int i,j;
    
    int next_line_mask = line_mask ^ current_line_mask;
    current_line_mask = line_mask;
    for(i=0;i<n;i++){
	if(next_line_mask % 2 && sum_lines[i] < 0){
	    flip_matrix_line(n,m,flip,i);
	    for(j=0;j<m;j++){
		sum_columns[j] = sum_column(n,m,flip,j);
	    }
	}
	next_line_mask /= 2;
    }
    
    int next_column_mask = column_mask ^ current_column_mask;
    current_column_mask = column_mask;
    for(i=0;i<m;i++){
	if(next_column_mask % 2 && sum_columns[i] < 0){
	    flip_matrix_column(n,m,flip,i);
	    for(j = 0;j<n;j++){
		sum_lines[j] = sum_line(n,m,flip,j);
	    }
	}
	next_column_mask /= 2;
    }
}


int main(){

    int n,m, i, j;
    FILE *f = fopen("flip.in","r");
    
    fscanf(f,"%d %d", &n, &m);
    int flip[n][m];
    int sum_lines[n], sum_columns[m];
    for(i=0;i<n;i++){
	for(j=0;j<m;j++){
	    fscanf(f,"%d", &flip[i][j]);
	}
    }
    
    int max_sum = sum_matrix(n,m,flip);
    int sum = 0;
    
    for(i=0;i<n;i++){
	sum_lines[i] = sum_line(n,m,flip,i);
    }
    for(j=0;j<m;j++){
	sum_columns[j] = sum_column(n,m,flip,j);
    }
    
//     printf("%d\n", sum_matrix(n,m,flip));
//     show_matrix(n,m,flip);
    for(i=1;i<=(1<<n);i++){
	for(j=1;j<=(1<<m);j++){
	    flip_matrix_by_mask(n,m,flip,sum_lines,sum_columns,i,j);
	    sum = sum_matrix(n,m,flip);
	    if(sum > max_sum){
		max_sum = sum;
	    }
	}

    }
//     printf("%d\n", max_sum);
//    show_matrix(n,m,flip);
    f = fopen("flip.out","w");
    fprintf(f,"%d",max_sum);
    fclose(f);

    return 0;
}