Cod sursa(job #733817)

Utilizator dorinmoldovanMoldovan Dorin dorinmoldovan Data 13 aprilie 2012 00:58:32
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

long b[32];
long a[32];
long m[16][16];
long N, M;
long step;

long sum(long m[16][16]){
    long sum = 0;
    for(long i = 0; i < N; i++)
        for(long j = 0; j < M; j++)
            sum = sum + m[i][j];
    return sum;
}

void back(long k, long &max, long h){
    long sumAux = 0;

    if(k - 1 == h){
        step++;
        long suma = sum(m);
        if(suma > max)
            max = suma;
    }
    if(k - 1 != h){
      for(long i = 1; i <= M + N; i++)
        if(!b[i] && a[k-1] < i){
            b[i] = 1;
            a[k] = i;
            if(i <= N){
                for(long j = 0; j <= M - 1; j++){
                    m[i-1][j] = -m[i-1][j];
                }
            }
            else{
                long col = i - N;
                for(long j = 0; j <= N - 1; j++){
                    m[j][col-1] = - m[j][col-1];
                }
            }

            back(k+1,max,h);
            b[i] = 0;
        }
    }
}

int main()
{
    long max = 0;
    ifstream f ("flip.in");
    f >> N;
    f >> M;

    for(long i = 0; i < N; i++)
        for(long j = 0; j < M; j++)
            f >> m[i][j];

    f.close();


    for (int i = 0; i <= N+M ; i++)
        back(1,max,i);


    ofstream g ("flip.out");
    g << max;
    g.close();

    return 0;
}