Pagini recente » Cod sursa (job #34594) | Cod sursa (job #177094) | Cod sursa (job #2301069) | Cod sursa (job #239809) | Cod sursa (job #1316519)
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<fstream>
using namespace std;
int a[17][17], ss[2][17], s[2][17] , maxx, sol_l[17], sol_c[17];
void reset_s(int n, int m){
for(int i=1;i<=n;i++){
s[0][i]=ss[0][i];
s[1][i]=ss[1][i];
}
}
void sum(int n,int m){
for(int i=1;i<=n;i++)
if(sol_l[i]==1){
int tmp=s[0][i];
s[0][i]=s[1][i] * (-1);
s[1][i]=tmp * (-1);
}
for(int j=1;j<=m;j++)
if(sol_c[j]==1)
for(int i=1;i<=n;i++){
if(a[i][j]<0){
s[1][i]=s[1][i]+a[i][j]*(-1);
s[0][i]=s[0][i]+a[i][j]*(-1);
}
else{
s[1][i]=s[1][i]+a[i][j]*(-1);
s[0][i]=s[0][i]-a[i][j];
}
}
int sum=0;
for(int i=1; i<=n;i++) sum=sum+s[0][i]+s[1][i];
if(sum>maxx) maxx=sum;
}
void back(int k, int n, int m, int w){
if(k==n+1 && w==0)
back(1,n,m,1);
else if(k==m+1 && w==1){
reset_s(n,m);
sum(n,m);
}
else{
if(w==0) {
sol_l[k]=-1;
while(sol_l[k]<1){
sol_l[k]++;
back(k+1,n,m,w);
}
}
else {
sol_c[k]=-1;
while(sol_c[k]<1){
sol_c[k]++;
back(k+1,n,m,w);
}
}
}
}
int main(){
int n,m;
ifstream in; ofstream out;
in.open("flip.in"); out.open("flip.out");
out.clear();
in>>n>>m;
for(int i=1;i<=n;i++){
int s_neg=0, s_poz=0;
for(int j=1;j<=m;j++){
in>>a[i][j];
if(a[i][j]>0) s_poz+=a[i][j];
else s_neg+=a[i][j];
}
ss[0][i]=s_poz;
ss[1][i]=s_neg;
}
reset_s(n,m);
maxx=16*16*1000000*(-1);
back(1,n,m,0);
out<<maxx;
return 0;
}