Cod sursa(job #1870768)

Utilizator bobotheslayerBogdan Zaharia bobotheslayer Data 6 februarie 2017 21:33:34
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,v[17][17],x[17],copiev[17][17],maxim=-999999;
FILE *intrare,*iesire;
void backtracking(int pos)
{
    int i,j,suma=0,k,sumamatrice=0;
    bool y=false;
    if (pos==n)
    {
        for (i=0; i<=n-1; ++i)
        {
            if (x[i]==1)
            {
                //inmultesc cu -1 LINIA marcata cu 1
                for (j=0; j<=m-1; ++j)
                {
                    v[i][j]=-1*v[i][j];
                }
            }
        }

        //dupa ce am inmultit cu -1 liniile din submultime, verific daca exista coloane negative sau nu,iar daca exista o inmultesc cu -1
        for (k=0; k<=m-1; ++k)
        {
            for (j=0; j<=n-1; ++j)
            {
                suma=suma+v[j][k];
            }
            if (suma<0)
            {
                for (j=0; j<=n-1; ++j)
                {
                    v[j][k]=-1*v[j][k];
                }
            }
            suma=0;
        }

        //fac suma matricii
        for (i=0; i<=n-1; ++i)
        {
            for (j=0; j<=m-1; ++j)
            {
                sumamatrice=sumamatrice+v[i][j];
            }
        }

        //aflu suma maxima si o afisez
        if (sumamatrice>maxim)
        {
            maxim=sumamatrice;
        }

        for (i=0; i<=n-1; ++i)
        {
            if (x[i]==1)
                y=true;
            else
            {
                y=false;
                break;
            }
        }
        if (y==true)
            fprintf(iesire,"%d",maxim);

        //reset-uri
        for (i=0; i<=n-1; ++i)
        {
            for (j=0; j<=m-1; ++j)
            {
                v[i][j]=copiev[i][j];
            }
        }
        sumamatrice=0;
    }
    else
    {
        for (i=0; i<=1; ++i)
        {
            x[pos]=i;
            backtracking (pos+1);
        }
    }
}

int main()
{
    int i,j;
    intrare=fopen("flip.in","r");
    iesire=fopen("flip.out","w");
    fscanf(intrare,"%d%d",&n,&m);
    for (i=0; i<=n-1; ++i)
    {
        for (j=0; j<=m-1; ++j)
        {
            fscanf(intrare,"%d",&v[i][j]);
            copiev[i][j]=v[i][j];
        }
    }

    backtracking(0);
}