Cod sursa(job #228007)

Utilizator Hori93Simon Horatiu Hori93 Data 6 decembrie 2008 10:02:24
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
 #include<fstream>  
 
 using namespace std;
      
    int st[17],n,m,k,as,ev,i,j,a[17][17],suma=0;  
      
    void init()  
    {   st[k]=-1;   }  
      
    int succ()  
    {  
       if(st[k]<1)  
       {  
          st[k]++;  
           return 1;  
       }  
       return 0;  
   }  
   int sol()  
   {  
       return k==n;  
   }  
   int valid()  
   {   return 1;   }  
     
     
   void solve()  
   {  
     
       int s=0,s1,b[17][17];  
       for(i=1;i<=n;i++)  
           for(j=1;j<=m;j++)  
               if(st[i]==1)  
                   b[i][j]=-a[i][j];  
               else  
                   b[i][j]=a[i][j];  
     
       for(i=1;i<=m;i++)  
           {  
           s1=0;  
           for(j=1;j<=n;j++)  
               s1+=b[j][i];  
           if(s1<0)  
               s+=-s1;  
           else  
               s+=s1;  
           }  
       if(s>suma)  
           suma=s;  
   }  
     
     
     
   void back()  
   {  
       k=1;  
       init();  
       while(k>0)  
       {  
           as=1;ev=0;  
           while(as&&!ev)  
           {  
               as=succ();  
               if(as)  ev=valid();  
           }  
           if(as)  
               if(sol())  
                   solve();  
               else  
               {  
                   k++;  
                   init();  
               }  
           else  
               k--;  
       }  
   }  
     
   int main()  
   {  
       ifstream f("flip.in");  
       ofstream g("flip.out");  
     
       f>>n>>m;  
     
       for(i=1;i<=n;i++)  
           for(j=1;j<=m;j++)  
               f>>a[i][j];  
     
     
       back();  
       g<<suma;  
       return 0;  
   }