Cod sursa(job #148952)

Utilizator vlad_olteanVladimir Oltean vlad_oltean Data 5 martie 2008 03:16:49
Problema Jocul Flip Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<fstream>
using namespace std;
int mat[20][20],m,n; // m-coloane, n-linii
int temp[20][20];
int st[20];
int uz[20];
int s,smax;
int col[5];

void back(int k)
{    int i,j;
     int a;

     if(k==n)   // actualizez suma
     {    for(i=0;i<m;i++) col[i]=0;

	      for(i=0;i<n;i++)  // fac flip pe linie cu 1/-1 din stiva
	           for(j=0;j<m;j++)
	           {    temp[i][j]=st[i]*mat[i][j];  // creez o matrice temp la care fac flip pe coloanele cu s<0
		            col[j]+=temp[i][j];
               }
	      for(j=0;j<m;j++)
	           if(col[j]<0)
	           {    col[j]=0;
		            for(i=0;i<n;i++)
			        col[j]+=-temp[i][j];
               }
	      s=0;
	      for(i=0;i<n;i++)
	           s+=col[i];
	      if(s>smax) smax=s;
	      //return;
     } else
     {    st[k]=1;
	      back(k+1);
		  st[k]=-1;
	      back(k+1);
     }
}

int main()
{   int i,j;
    ifstream fin("flip.in");
    ofstream fout("flip.out");

    fin>>n>>m;
    for(i=0;i<n;i++)
  	     for(j=0;j<m;j++)
	          fin>>mat[i][j];

    back(0);
    fout<<smax;
    fin.close(); fout.close();
    return 0;
}