Cod sursa(job #803185)

Utilizator yamahaFMI Maria Stoica yamaha Data 27 octombrie 2012 10:40:56
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#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;
}