Cod sursa(job #733823)

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

int b[32];
int a[32];
int m[16][16];
int N, M;

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

void back(int k, int &max, int h){
    if(k - 1 == h){
        int 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;
            int xx = 0;
            if(i <= N){
                for(int j = 0; j <= M - 1; j++){
                    m[i-1][j] = -m[i-1][j];
                    xx = xx + m[i-1][j];
                }
            }
            else{
                int col = i - N;
                for(int j = 0; j <= N - 1; j++){
                    m[j][col-1] = - m[j][col-1];
                    xx = xx + m[j][col-1];
                }
            }
            if(xx < 0){
                b[i] = 0;
                return;
            }
            back(k+1,max,h);
            b[i] = 0;
        }
    }
}

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

    for(int i = 0; i < N; i++)
        for(int 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;
}