Cod sursa(job #2457433)

Utilizator bori2000Fazakas Borbala bori2000 Data 17 septembrie 2019 18:57:55
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
using namespace std;

int n, m;
int a[17][17];

int ossz[17]; //i. oszlop elemeinek osszege
int aktossz[17];

int maxered;
int ered;

void backtrack(int arow){
    if(arow<=n)
   {
       //2.eset: nem forditom meg az arow sort
       //cout<<"not flipped "<<arow<<endl;
       backtrack(arow+1);


       //1. eset megforditom az arow sort
        for(int i=1; i<=m; i++)
        {
            aktossz[i]-=2*a[arow][i];
        }
        //cout<<"flipped "<<arow<<endl;
        backtrack(arow+1);

        //ertekek visszaallitasa
        for(int i=1; i<=m; i++)
        {
            aktossz[i]+=2*a[arow][i];
        }
   }
   else
   {
       ered=0;
       for(int i=1; i<=m; i++)
       {
           ered+=abs(aktossz[i]);
       }
       //cout<<"ered = "<<ered<<endl;
       if(ered>maxered) maxered=ered;
   }

}

int main()
{
    ifstream f("flip.in");
    ofstream g("flip.out");

    f>>n>>m;

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(j==1) aktossz[j]=0;
            f>>a[i][j];
            ossz[j]+=a[i][j];
        }
    }

    for(int i=1; i<=m; i++)
    {
        aktossz[i]=ossz[i];
    }

    maxered=0;

    backtrack(1);

    g<<maxered;



    return 0;
}