Pagini recente » Cod sursa (job #683856) | Cod sursa (job #2183629) | Istoria paginii runda/rs1/clasament | Monitorul de evaluare | Cod sursa (job #2003250)
#include <iostream>
#include <fstream>
int max_sum=-100000;
using namespace std;
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);
for(int i = 0 ; i<w+h;i++)
{
//cout<<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;
//printMat(mat,w,h);
// cout<<tmp_sum<<">"<<branch_max_sum<<endl;
// cin.get();
bt(mat,w,h);
}
flip(mat,w,h,i);
}
}
int main()
{
ifstream input ("flip.in");
ofstream output("flip.out");
int w,h,p;
int **mat;
int * s;
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;
}