Pagini recente » Cod sursa (job #877592) | Cod sursa (job #960691) | Cod sursa (job #1566488) | Cod sursa (job #964079) | Cod sursa (job #964083)
Cod sursa(job #964083)
#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;
}
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;
}