Cod sursa(job #2119477)

Utilizator catalinlupCatalin Lupau catalinlup Data 1 februarie 2018 11:53:01
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 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;
map<int,bool> LinFlipped;
map<int,bool> ColFlipped;
int smax=-1;
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];
        }
    }
}

void Flip(int num,int tip){
    if(tip==LINIE){
        for(int i=1;i<=M;i++)
            Map[num][i]*=-1;
    }
    else if(tip==COLOANA){
        for(int i=1;i<=N;i++){
            Map[i][num]*=-1;
        }
    }
}

int Sum(){
    int s=0;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            s+=Map[i][j];
        }
    }
    return s;
}

void Backtrack(){
    smax=max(smax,Sum());
    for(int i=1;i<=N;i++){
        if(!LinFlipped[i]){
            LinFlipped[i]=true;
            Flip(i,LINIE);
            Backtrack();
            Flip(i,LINIE);
            LinFlipped[i]=false;
        }
    }
    for(int i=1;i<=M;i++){
        if(!ColFlipped[i]){
            ColFlipped[i]=true;
            Flip(i,COLOANA);
            Backtrack();
            Flip(i,COLOANA);
            ColFlipped[i]=false;
        }
    }
}

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