Pagini recente » Cod sursa (job #2976220) | Cod sursa (job #329000) | Cod sursa (job #583382) | Cod sursa (job #2206147) | Cod sursa (job #1316422)
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<fstream>
using namespace std;
int a[17][17], aa[17][17], maxx, sol_l[17], sol_c[17];
void reset_a(int n, int m){
for(int i=1;i<=n;i++)
for(int j=1;j<=m; j++){
a[i][j]=aa[i][j];
}
}
void sum(int n, int m){
int s=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(sol_c[j]==1) a[i][j]=a[i][j]*(-1);
if(sol_l[i]==1) a[i][j]=a[i][j]*(-1);
s=s+a[i][j];
}
}
if(s>maxx) maxx=s;
}
/*find all the subsets i of {1,2,..,n} => lines to be multiplied by (-1)
for each i find all the subsets j of {1,2,..,m} => cols to be multiplied by (-1)
*/
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_a(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++)
for(int j=1;j<=m;j++)
in>>aa[i][j];
reset_a(n,m);
maxx=16*16*1000000*(-1);
back(1,n,m,0);
out<<maxx;
return 0;
}