Pagini recente » Cod sursa (job #1238941) | Cod sursa (job #1754078) | Cod sursa (job #1667082) | Cod sursa (job #903848) | Cod sursa (job #772441)
Cod sursa(job #772441)
#include <stdio.h>
#include <stdlib.h>
typedef struct flip {
int m, n;
int board[16][16];
int sw[16];
int max_sum;
} flip_t;
void read_input( flip_t *flip )
{
int i, j;
scanf( "%d %d", &flip->m, &flip->n );
for ( i = 0; i < flip->m; i++ ) {
for ( j = 0; j < flip->n; j++ ) {
scanf( "%d", &flip->board[i][j] );
}
}
}
void write_output( flip_t *flip )
{
printf( "%d\n", flip->max_sum );
}
void compute_sum( flip_t *flip )
{
int i, j;
int sum = 0, s;
for ( j = 0; j < flip->n; ++j ) {
s = 0;
for ( i = 0; i < flip->m; ++i ) {
if ( flip->sw[i] == 1 ) {
s -= flip->board[i][j];
} else {
s += flip->board[i][j];
}
}
if ( s < 0 ) {
sum -= s;
} else {
sum += s;
}
}
if ( sum > (flip->max_sum) ) {
flip->max_sum = sum;
}
}
void backtracking( flip_t *flip )
{
int i;
do {
compute_sum( flip );
i = flip->m - 1;
while( flip->sw[i] == 1 && i >= 0 ) {
flip->sw[i--] = 0;
}
if ( i < 0 ) {
return;
}
flip->sw[i] = 1;
} while( 1 );
}
int main( void )
{
flip_t flip = {};
freopen( "flip.in", "r", stdin );
freopen( "flip.out", "w", stdout );
read_input( &flip );
backtracking( &flip );
write_output( &flip );
return EXIT_SUCCESS;
}