Mai intai trebuie sa te autentifici.
Cod sursa(job #1660179)
Utilizator | Data | 22 martie 2016 21:08:02 | |
---|---|---|---|
Problema | Jocul Flip | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.35 kb |
#include <iostream>
#include <fstream>
#define NMAX 16
using namespace std;
int N, M; // dimensiunile tablei
int board[NMAX][NMAX]; // tabla de joc
int solution[2 * NMAX]; // contine 1 sau -1 pe fiecare pozitie, adica cu cat sa se inmulteasca liniile si coloanele
int maxSum = 0; // retine suma maxima obtinuta pentru fiecare configuratie
void read() {
// dimensiunile matricei
scanf("%d %d", &N, &M);
// elementele matricei
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%d", &board[i][j]);
}
}
}
// calculeaza suma de pe tabla si o compara cu maximul curent
void computeSum() {
int sum = 0;
// calculeaza suma
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
sum += board[i][j] * solution[i] * solution[N + j];
}
}
// actualizeaza suma maxima
if (sum > maxSum) {
maxSum = sum;
}
}
// pe pozitia k adauga 1 sau -1
void backtrack(int k) {
// daca a ajuns la sfarsitul backtracking-ului, programul face suma de pe tabla
if (k >= N + M) {
computeSum();
return;
}
for (int i = 1; i >= -1; i -= 2) {
solution[k] = i;
backtrack(k + 1);
}
}
int main() {
freopen("flip.in", "r", stdin);
freopen("flip.out", "w", stdout);
read();
backtrack(0);
cout << maxSum;
}