Cod sursa(job #737688)

Utilizator dorinmoldovanMoldovan Dorin dorinmoldovan Data 20 aprilie 2012 01:11:03
Problema Jocul Flip Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.35 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int result(){
    int s = 0;
    for(int i = 0; i <= N - 1; i++)
        for(int j = 0; j <= M - 1; j++)
            s = s + m[i][j];
    return s;
}

void transform(int sel, int i){
    if(sel == 1)
        for(int j = 0; j <= N - 1; j++)
            m[j][i] = - m[j][i];
    if(sel == 2)
        for(int j = 0; j <= M - 1; j++)
            m[i][j] = - m[i][j];
    return;
}

int verify(int sel, int i){
    int ok = 0;
    int sum = 0;
    if(sel == 1){
        for(int j = 0; j <= N - 1; j++)
            sum = sum + m[j][i];
        if(sum >= 0) ok = 1;
    }
    if(sel == 2){
        for(int j = 0; j <= M - 1; j++)
            sum = sum + m[i][j];
        if(sum >= 0) ok = 1;
    }
    return ok;
}

void transfigure(int sel){
    if(sel == 1)
        for(int i = 0; i <= N - 1; i++)
            if(a[N-i] == 1)
            transform(3 - sel, i);
    if(sel == 2)
        for(int i = 0; i <= M - 1; i++)
            if(a[M-i] == 1)
            transform(3 - sel, i);
    return;
}

void print(){
    for(int i = 0; i <= N - 1; i++){
        for(int j = 0; j <= M - 1; j++) cout << m[i][j] << " ";
        cout << "\n";
    }
    cout << "\n";
    return;
}

void binary(int m, int sel, int &max){
    int p;
    if( m == 0)
        {
           print();
           if(sel == 1){
                for(int j = 0; j <= M - 1; j++)
                    if(verify(sel,j) == 0){
                        transform(sel,j);
                        b[j] = 1;
                    }
                p = 0;
                for(int i = 0; i <= N - 1; i++)
                    if(verify(3 - sel, i) == 0)
                        p = 1;
                if(p == 0) if(result() > max) max = result()
                ;
                for(int j = 0; j <= M - 1; j++)
                    if(b[j] == 1){
                        transform(sel,j);
                        b[j] = 0;
                    }
           }

           if(sel == 2){
                for(int j = 0; j <= N - 1; j++)
                    if(verify(sel,j) == 0){
                        transform(sel,j);
                        b[j] = 1;
                    }
                print();
                p = 0;
                for(int i = 0; i <= M - 1; i++)
                    if(verify(3 - sel, i) == 0)
                        p = 1;
                if(p == 0) if(result() > max) max = result();
                for(int j = 0; j <= N - 1; j++)
                    if(b[j] == 1){
                        transform(sel,j);
                        b[j] = 0;
                    }
           }

        }
    else{
        a[m] = 0; binary(m-1,sel,max);
        a[m] = 1; transform(3-sel, m-1); binary(m-1,sel,max); transform(3-sel , m- 1);
    }
    return;
}

int main()
{
    int max = 0;
    int min;
    int sel;
    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();

    if (N < M){
        min = N;
        sel = 1;
    }
    else {
        min = M;
        sel = 2;
    }

    binary(min,sel,max);

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

    return 0;
}