Cod sursa(job #2003253)

Utilizator trandafirpatrickTrandafir Patrick trandafirpatrick Data 22 iulie 2017 14:56:58
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#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);
    cout<<max_sum;

    return 0;
}