Cod sursa(job #1316422)

Utilizator b10nd3Oana Mancu b10nd3 Data 13 ianuarie 2015 20:06:56
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<fstream>


using namespace std;


int a[17][17], aa[17][17],  maxx, sol_l[17], sol_c[17];

void reset_a(int n, int m){
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m; j++){
	  	a[i][j]=aa[i][j];
	  }
}


void sum(int n, int m){
	    int s=0;
		for(int i=1;i<=n;i++){
	      	for(int j=1;j<=m;j++){
		       if(sol_c[j]==1) a[i][j]=a[i][j]*(-1);
			   if(sol_l[i]==1) a[i][j]=a[i][j]*(-1); 
			   s=s+a[i][j]; 
		     }
		}
		if(s>maxx) maxx=s;
}





/*find all the subsets i of {1,2,..,n} => lines to be multiplied by (-1) 
  for each i find all the subsets j of {1,2,..,m}  => cols to be multiplied by (-1)
*/

void back(int k, int n, int m, int w){
	if(k==n+1 && w==0) 
	    back(1,n,m,1);
	else if(k==m+1 && w==1){
        reset_a(n,m); 
		sum(n,m);
	}
    else{
   	    if(w==0) {
   	    	sol_l[k]=-1;
            while(sol_l[k]<1){
   	          sol_l[k]++;
			  back(k+1,n,m,w);
		    }
		 }
   	    else {
   	    	sol_c[k]=-1;
            while(sol_c[k]<1){
   	          sol_c[k]++;
   	    	  back(k+1,n,m,w);
   	         }
		   }    
   	}
}



int main(){

int n,m;

ifstream in; ofstream out;
in.open("flip.in"); out.open("flip.out");
out.clear();

in>>n>>m; 
for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)
      in>>aa[i][j]; 
	  
reset_a(n,m);
maxx=16*16*1000000*(-1);

back(1,n,m,0);

out<<maxx;

return 0;	
}