Pagini recente » Cod sursa (job #2323823) | Cod sursa (job #2614323) | Cod sursa (job #664834) | Cod sursa (job #2204215) | Cod sursa (job #803185)
Cod sursa(job #803185)
#include<fstream>
#include<conio.h>
#include<iostream>
using namespace std;
int sol[36];
int N, M, v[18][18];
int valid(int nivel, int actual){
for(int i=1; i<nivel; i++){
if(sol[i]==actual) return 0;
}
return 1;
}
void writeSol(int p, int sum, int& max){
int i,j;
for(i=1; i<=p; i++){
if(sol[i]<=N){ // dc sunt linii
for(j=1; j<=M; j++){ // schimbam semnul pe linia respectiva
sum += 2*(-v[sol[i]][j]);
}
}
else{ // dc sunt coloane
for(j=1; j<=N; j++){ // schimbam semnul pe coloana respectiva: pt a comuta coloane, i = N+1 ... N+M
sum += 2*(-v[j][sol[i]-N]);
}
}
}
if(sum > max) max = sum;
}
void back(int nivel, int n, int p, int sum, int& max){ // A de N+M luate cate p
if(nivel == p+1) { writeSol(p,sum,max); return; } // are solutia
for(int i=1; i<=n; i++){ // valorile cu care se completeaza 1, 2, ... n
if(valid(nivel, i)){ // nivelul e de la 1 la p
sol[nivel] = i;
back(nivel+1, n, p, sum, max);
}
}
}
int main (){
ifstream f("flip.in");
f>>N>>M;
int sum=0, max;
int i, j; // sum = suma intregii table nemodificate
for(i=1;i<=N;i++){ // linii
for(j=1; j<=M; j++){ // coloane
f>>v[i][j];
sum += v[i][j];
}
}
max = sum;
// avem de facut aranjamente de N+M luate cate 1, 2, 3 ... N+M pentru a verifica toate posibilitatile
int p;
for(p=1; p<=N+M; p++)
back(1,N+M,p,sum,max);
ofstream g("flip.out");
g<<max;
return 0;
}