Cod sursa(job #734151)

Utilizator dorinmoldovanMoldovan Dorin dorinmoldovan Data 13 aprilie 2012 17:50:51
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <iostream>
#include <fstream>

using namespace std;

int N, M;
int m[16][16];
int b[32];
int suma ,max;
int sum(int m[16][16]){
    int sum = 0;
    for(int i = 0; i <= N - 1; i++)
        for(int j = 0; j <= M - 1; j++)
            sum = sum + m[i][j];
    return sum;
}

int transform(int m[16][16]){
    for(int i = 0; i <= N - 1; i++){
        if(b[i+1] == 1)
            for(int j = 0; j <= M - 1; j++)
                m[i][j] = - m[i][j];
    }
    for(int j = 0; j <= M - 1; j++){
        if(b[N+1+j] == 1)
            for(int i = 0; i<= N - 1; i++)
                m[i][j] = -m[i][j];
    }
}


int validate(int i){
    int v = 1;
    int sum = 0;
    if(i >= 1 && i <= N)
        for(int j = 0; j <= M - 1; j++)
            sum = sum + m[i-1][j];
    else if(i >= N + 1 && i <= M + N){
        for(int j = 0; j <= N - 1; j++)
            sum = sum + m[j][i-N-1];}
    else v = 0;
    if(sum < 0){
        v = 0;
    }
    return v;
}

void transform(int i){
    if(i >= 1 && i <= N)
        for(int j = 0; j <= M - 1; j++)
            m[i-1][j] = -m[i-1][j];
    else if(i >= N + 1 && i <= M + N)
        for(int j = 0; j <= N - 1; j++)
            m[j][i-N-1] = -m[j][i-N-1];
}

void back(int k, int h, int &ok, int &max){

    if(h == M + N + 1){
    //   for(int i = 1; i <= M + N; i++)
    //        cout << b[i];
    //        cout << "\n";
        transform(m);
        suma = sum(m);
        if(suma > max)
            max = suma;
        h = 0;
    }
    else {
        for(int i = h + 1; i <= M + N + 1; i++)
        {
            if(b[i] == 0 && ok == 1)
                {

                    transform(i);
                    if(validate(i) == 0){ok = 0; }
                    transform(i);
                    b[i] = 1;
                    h = h + 1;
                    back(k+1,h,ok,max);

                    if(ok == 0)
                    b[i] = 0;
                    ok = 1;

                }

        }
    }
}

int main()
{
    int max = 0;

    ifstream fin ("flip.in");
    fin >> N;
    fin >> M;

    for(int i = 0; i <= N - 1; i++)
        for(int j = 0; j <= M - 1; j++)
            fin >> m[i][j];

    fin.close();

    int h = 0;
    int ok = 1;
    back(1,h,ok,max);

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

    return 0;
}