Pagini recente » Cod sursa (job #3258167) | Cod sursa (job #2568969) | Cod sursa (job #1722118) | Cod sursa (job #1347604) | Cod sursa (job #2119477)
#include <iostream>
#include <bits/stdc++.h>
#define INFILE "flip.in"
#define OUTFILE "flip.out"
#define COLOANA 1
#define LINIE 0
using namespace std;
const int NMAX=20;
int N,M;
array<array<int,NMAX>,NMAX> Map;
map<int,bool> LinFlipped;
map<int,bool> ColFlipped;
int smax=-1;
ifstream in(INFILE);
ofstream out(OUTFILE);
void Read(){
in>>N>>M;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
in>>Map[i][j];
}
}
}
void Flip(int num,int tip){
if(tip==LINIE){
for(int i=1;i<=M;i++)
Map[num][i]*=-1;
}
else if(tip==COLOANA){
for(int i=1;i<=N;i++){
Map[i][num]*=-1;
}
}
}
int Sum(){
int s=0;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
s+=Map[i][j];
}
}
return s;
}
void Backtrack(){
smax=max(smax,Sum());
for(int i=1;i<=N;i++){
if(!LinFlipped[i]){
LinFlipped[i]=true;
Flip(i,LINIE);
Backtrack();
Flip(i,LINIE);
LinFlipped[i]=false;
}
}
for(int i=1;i<=M;i++){
if(!ColFlipped[i]){
ColFlipped[i]=true;
Flip(i,COLOANA);
Backtrack();
Flip(i,COLOANA);
ColFlipped[i]=false;
}
}
}
int main()
{
Read();
Backtrack();
out<<smax<<"\n";
return 0;
}