Pagini recente » Cod sursa (job #589724) | Cod sursa (job #1430320) | Cod sursa (job #1645672) | Cod sursa (job #868263) | Cod sursa (job #2003254)
#include <iostream>
#include <fstream>
int max_sum=-100000;
using namespace std;
int getMin(int * arr,int l){
int min = arr[0];
int pos=0;
for(int i = 1 ; i < l; i++){
if(arr[i]<min){
pos=i;
min=arr[i];
}
}
if(min>=0)
return -1;
else
return pos;
}
void printMat(int ** mat,int w,int h){
cout<<endl;
for(int i = 0;i<w;i++){
for(int j = 0;j<h;j++){
cout<<mat[i][j]<<" ";
}
cout<<endl;
}
}
int matSum(int ** mat, int w , int h){
int total=0;
for(int i = 0;i<w;i++){
for(int j = 0;j<h;j++){
total+=mat[i][j];
}
}
return total;
}
int * sum(int **mat,int w,int h){
int *s = new int[w+h]();
for(int i = 0;i<w;i++){
for(int j = 0;j<h;j++){
s[i]+=mat[i][j];
s[w+j]+=mat[i][j];
}
}
return s;
}
void flip(int **mat, int w,int h,int nr){
if(nr>=w){
for(int i = 0 ; i < w;i++)
mat[i][nr-w]*=-1;
}
else{
for(int i = 0 ; i < h;i++)
mat[nr][i]*=-1;
}
}
void bt(int ** mat,int w,int h){
int branch_max_sum=matSum(mat,w,h);
int * s=sum(mat,w,h);
if(getMin(s,w+h)==-1)
return;
for(int i = 0 ; i<w+h;i++)
{
flip(mat,w,h,i);
int tmp_sum=matSum(mat,w,h);
if(tmp_sum>branch_max_sum)
{
if(tmp_sum>max_sum)
max_sum=tmp_sum;
bt(mat,w,h);
}
flip(mat,w,h,i);
}
}
int main()
{
ifstream input ("flip.in");
ofstream output("flip.out");
int w,h;
int **mat;
input>>w>>h;
mat=new int* [w];
for(int i = 0 ; i < w ; i++){
mat[i]=new int[h];
for(int j = 0;j<h;j++){
input>>mat[i][j];
}
}
max_sum=matSum(mat,w,h);
bt(mat,w,h);
output<<max_sum;
return 0;
}