Cod sursa(job #1316519)

Utilizator b10nd3Oana Mancu b10nd3 Data 13 ianuarie 2015 21:28:59
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<fstream>



using namespace std;


int a[17][17], ss[2][17], s[2][17] , maxx, sol_l[17], sol_c[17];

void reset_s(int n, int m){
	for(int i=1;i<=n;i++){
	  s[0][i]=ss[0][i]; 
	  s[1][i]=ss[1][i]; 
	}
	  
}


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





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_s(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++){
   int s_neg=0, s_poz=0;
   for(int j=1;j<=m;j++){
      in>>a[i][j]; 
      if(a[i][j]>0) s_poz+=a[i][j];
      else      s_neg+=a[i][j];
  }
  ss[0][i]=s_poz;
  ss[1][i]=s_neg;
}
	  
reset_s(n,m);
maxx=16*16*1000000*(-1);

back(1,n,m,0);

out<<maxx;

return 0;	
}