#include <iostream>
#include <fstream>
#include <limits>
using namespace std;
#define ARR_SIZE 16
int matMax[ARR_SIZE][ARR_SIZE];
/* Compute sum by parsing the whole array */
int compute_sum(int mat[][ARR_SIZE], int m, int n)
{
int sum = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
{
sum += mat[i][j];
}
return sum;
}
/* flip_row */
void flip_row(int mat[][ARR_SIZE], int i, int j, int m, int n, int &sum)
{
for(int k = 0; k < n; k++)
{
mat[i][k] = - mat[i][k];
sum += 2*mat[i][k]; //the relative difference between the sum obtained by a new flip
}
}
/* flip_column */
void flip_column(int mat[][ARR_SIZE], int i, int j, int m, int n, int &sum)
{
//return sum;
for(int k = 0; k < m; k++)
{
mat[k][j] = - mat[k][j];
sum += 2*mat[k][j]; //the relative difference between the sum obtained by a new flip
}
}
void next(int mat[][ARR_SIZE], int i, int j, int m, int n, int &sum, int &sumMax)
{
//stop condition
if(i == m-1 && j == n-1)
return;
//check the current solution
if(sum > sumMax)
{
sumMax = sum;
//std::copy(&mat[0][0], &mat[0][0]+m*n,&matMax[0][0]);
}
//generate next steps
if(j < n-1)
j++;
else
{
i++;
j = 0;
}
//i, j
//next(mat,i,j,m,n,sum,sumMax);
//i, j - flipped
flip_column(mat,i,j,m,n,sum);
next(mat,i,j,m,n,sum,sumMax);
flip_column(mat,i,j,m,n,sum);
//i - flipped, j
flip_row(mat,i,j,m,n,sum);
next(mat,i,j,m,n,sum,sumMax);
//i - flipped, j - flipped
flip_column(mat,i,j,m,n,sum);
next(mat,i,j,m,n,sum,sumMax);
}
void read_from_file(int mat[][ARR_SIZE], ifstream &in, int m, int n)
{
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
in >> mat[i][j];
}
}
}
int main()
{
char in_title[30] = "flip.in";
char out_title[30] = "flip.out";
ifstream in(in_title,ios::in);
ofstream out(out_title,ios::out);
int m, n;
in >> m >> n;
int mat[ARR_SIZE][ARR_SIZE];
//read from input file
read_from_file(mat, in, m, n);
//initialize the sum and the global maximum sum
int sum = compute_sum(mat, m, n);
int sumMax = sum;
/* next step having a matrix, current coordinates, matrix size, current sum, and the maximum sum */
next(mat,0,0,m,n,sum,sumMax);
out << sumMax;
in.close();
out.close();
return 0;
}