Cod sursa(job #2119500)

Utilizator catalinlupCatalin Lupau catalinlup Data 1 februarie 2018 12:35:46
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <iostream>
#include <bits/stdc++.h>
#define INFILE "flip.in"
#define OUTFILE "flip.out"
#define COLOANA 1
#define LINIE 0
using namespace std;
const int NMAX=20;
int N,M;
array<array<int,NMAX>,NMAX> Map;
int smax=-1;
array<bool,2*NMAX> Flip;
ifstream in(INFILE);
ofstream out(OUTFILE);
void Read(){
    in>>N>>M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            in>>Map[i][j];
        }
    }
}



int Sum(){
    array<array<int,NMAX>,NMAX> provArray;
   for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            provArray[i][j]=Map[i][j];
        }
    }
    for(int i=1;i<=N;i++){
        if(Flip[i]){
            for(int j=1;j<=M;j++)
                provArray[i][j]=-provArray[i][j];
        }
    }
    for(int j=N+1;j<=N+M;j++){
        if(Flip[j]){
            for(int i=1;i<=N;i++){
                provArray[i][j-N]=-provArray[i][j-N];
            }
        }
    }
    int s=0;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            s+=provArray[i][j];
        }
    }
    return s;
}

void Backtrack(int k){
    if(k==M+N+1){
        smax=max(smax,Sum());
        //cout<<smax<<endl;
    }
    else{
        Flip[k]=true;
        Backtrack(k+1);
        Flip[k]=false;
        Backtrack(k+1);
    }
}

int main()
{
    Read();
    Backtrack(1);
    out<<smax<<"\n";
    return 0;
}