Cod sursa(job #964084)

Utilizator danlexDan Alexandru danlex Data 20 iunie 2013 01:26:53
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <iostream>
#include <fstream>
using namespace std;

int i, j, k, n, m, st, x[100], game[16][16], localGame[16][16], maxGame, sumGame, countMinus = 0, countPlus = 0, countZero = 0;
bool DEBUG = false;

void print(){
    cout << endl;
    cout << "sumGame: " << sumGame << endl;
    cout << "maxGame: " << maxGame << endl;
    for (i = 0; i < m + n; i ++){
        cout << x[i] << " ";
    }
    cout << endl;
    for (i = 0; i < n; i ++){
        for (j = 0; j < m; j++){
            cout << localGame[i][j] << " ";
        }
        cout << endl;
    }
}

void read(){
    ifstream f("flip.in");
    f >> n;
    f >> m;

    for (i = 0; i < n; i++){
        for (j = 0; j < m; j++){
            f >> game[i][j];
            if (game[i][j] < 0) countMinus ++;
            else if (game[i][j] > 0) countPlus ++;
            else countZero ++;
        }
    }

    if(DEBUG) cout << "n = " << n << endl;
    if(DEBUG) cout << "m = " << m << endl;

    f.close();
}

void write(){
    ofstream of("flip.out");
    of << maxGame;
    of.close();

}

bool cond(){
    return true;
}

int computeGame(){
    for (i = 0; i < n; i ++){
        for(j = 0; j < m; j ++){
            localGame[i][j] = game[i][j];
        }
    }
    for (k = 0; k < n; k ++){
        if (x[k] == 1)
        for (j = 0; j < m; j ++){
            localGame[k][j] *= -1;
        }
    }

    for (k = 0; k < m; k ++){
        if(x[k + n] == 1)
        for (i = 0; i < n; i ++){
            localGame[i][k] *= -1;
        }
    }

    sumGame = 0;
    for (i = 0; i < n; i++){
        for (j = 0; j < m; j++){
            sumGame += localGame[i][j];
        }
    }

    return sumGame;
}

bool worst(){
    bool worst = false;
    if(countPlus + countZero == m * n){
        if (DEBUG) cout << "countPlus " << endl;
        worst = true;
    }

    if(countMinus + countZero == m * n){
        if (DEBUG) cout << "countMinus " << endl;
        for (i = 0; i < n; i ++){
            x[i] = 1;
        }
        worst =  true;
    }

    if (worst){
        maxGame = sumGame = computeGame();
        if (DEBUG) print();
    }
    return worst;
}

void back(){
    st = 0;
    x[st] = -1;
    while (st >= 0) {
          if (x[st] < 1){
               x[st] ++;
               if (cond()){
                  if (st == n + m -1){
                      maxGame = max(maxGame, sumGame = computeGame());
                      if (DEBUG && maxGame == sumGame) print();
                  } else {
                     st ++;
                     x[st] = -1;
                  }
               }
           } else {
               st --;
           }
    }
}

int main(void)
{
    read();
    if (!worst()){
        back();
    }
    write();
    return 0;
}