Cod sursa(job #1524726)

Utilizator preda.andreiPreda Andrei preda.andrei Data 14 noiembrie 2015 13:17:47
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <stdio.h>

using namespace std;

int mat[20][20];
char v[20][2];

int suma(int n, int m){
    int s=0;

    for(int i=1; i<=n; ++i)
        if(v[i][0]=='+')
            s+=mat[i][0];
        else s-=mat[i][0];

    for(int i=1; i<=m; ++i){
        if(v[i][1]=='-'){
            s-=2*mat[0][i];
        }
    }

    return s;
}

void backtracking(int i, int n, int m, int &smax){
    if(i==n*m+1){
        int sum=suma(n, m);
        if(sum>smax)
            smax=sum;
        return;
    }

    int col=0, lin=i;

    if(i>n){
        lin=i-n;
        col=1;
    }

    v[lin][col]='+';
    backtracking(i+1, n, m, smax);
    v[lin][col]='-';
    backtracking(i+1, n, m, smax);
}

int main()
{
    FILE *fin=fopen("flip.in", "r");
    FILE *fout=fopen("flip.out", "w");

    int n, m, smax=0;

    fscanf(fin, "%d%d", &n, &m);
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            fscanf(fin, "%d", &mat[i][j]);
            mat[i][0]+=mat[i][j];
            mat[0][j]+=mat[i][j];
        }
    }

    backtracking(1, n, m, smax);

    fprintf(fout, "%d", smax);
    return 0;
}