Cod sursa(job #2091139)

Utilizator cocacola0tura adi cocacola0 Data 19 decembrie 2017 10:41:21
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#define MAX 17
using namespace std;

ifstream fin("flip.in");
ofstream fout("flip.out");

int s[MAX][MAX],viz[MAX][MAX],n,m,a[MAX][MAX],smax;

void citire()
{
    int i,j;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            fin>>a[i][j];
}

void afis()
{
    int i;
    for(i=1;i<=n;i++)
        fout<<s[1][i]<<" ";
    fout<<endl;
    for(i=1;i<=m;i++)
        fout<<s[2][i]<<" ";

    fout<<endl<<endl;
}

int sum()
{
    int suma=0,i,j;

    for(i=1;i<=n;i++)
        if(s[1][i]==1)
            for(j=1;j<=m;j++)
                a[j][i]*=-1;

    for(i=1;i<=m;i++)
        if(s[2][i]==1)
            for(j=1;j<=n;j++)
                a[i][j]*=-1;

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            suma+=a[i][j];

    return suma;
}

void backt(int i,int j)
{
    int q,w,suma;

    if(i>n && j>m)
    {
        afis();
        int suma=sum();

        if(suma>smax)
            smax=suma;

        fout<<suma<<endl;
    }

    if(i<=n)
        for(q=0;q<=1;q++)
        {
            s[1][i]=q;
            backt(i+1,j);
        }
    else
        if(j<=m)
            for(w=0;w<=1;w++)
            {
                s[2][j]=w;
                backt(i,j+1);
            }
}

int main()
{
    citire();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            smax+=a[i][j];

    backt(1,1);
    fout<<smax;
    return 0;
}