Cod sursa(job #681032)

Utilizator djgaby128Suciu Remus Gabriel djgaby128 Data 16 februarie 2012 13:45:49
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
//#include<iostream>
#include<fstream>
using namespace std;
ifstream f;
ofstream g;

long a[16][16];
int n,m,i,j;
int k,k2,cc,maxim,x;

int st[16],stc[16];

void init(int s[16])
{
    for(int i=1;i<=m;i++)
        s[i]=0;
}
/*
void afisare()
{
 for(i=1;i<=n;i++)
 {
        for(j=1;j<=m;j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
 }

}
*/
void comutal(int l)
{
    int j;
        for(j=1;j<=m;j++)
            a[l][j]=-a[l][j];
}
void comutac(int c)
{
    int i;
    for(i=1;i<=n;i++)
             a[i][c]=-a[i][c];
}
/*
long sumal(int l)
{
    long s=0;
    int j;
        for(j=1;j<=m;j++)
            s=s+a[l][j];
    return s;
}
long sumac(int c)
{
     long s=0;
     int i;
    for(i=1;i<=n;i++)
             s=s+a[i][c];
    return s;

}
*/
int sumat()
{
    int csuma=0;

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        csuma+=a[i][j];
    }
    return csuma;
}

//backtracking pt coloane

int solutiec(int k2)
{
	return(k2==m+1);
}
void tiparc(int k2)
{
  for(int i=1;i<=m;i++)
    {
        //cout<<stc[i]<<" ";
        if (stc[i]==2)
        comutac(i);
        x=sumat();
            if(maxim<x)
              maxim=x;
    }
    //cout<<endl;
}

int validc(int k2)
{
int ok=1;
/*for(int i=1;i<=k-1;i++)
	if(st[k]==st[i])
		ok=0;*/
return ok;
}
int succesorc(int k2)
{
	int ok=1;
	  if (stc[k2]<2)
          stc[k2]++;
	  else
		  ok=0;
	return ok;
}
void back2(int k2)
{
if(solutiec(k2))
    tiparc(k2);
else
  while(succesorc(k2))
  {
    //    if(validc(k))
		{
			stc[k2+1]=0;
		   back2(k2+1);

		}
  }

}

//backtracking pt linii

int solutie(int k)
{
	return(k==n+1);
}
void tipar(int k)
{
  for(int i=1;i<=n;i++)
    {
        //cout<<st[i]<<endl;;
        for(int j=1;j<=n;j++)
            //cout<<st[j]<<" ";
        //cout<<endl;
        if (st[i]==2)
        comutal(i);
        x=sumat();
            if(maxim<x)
              maxim=x;
 //       init(stc);
 //       back2(1);
    }
    //cout<<endl;
}

int valid(int k)
{
int ok=1;
/*for(int i=1;i<=k-1;i++)
	if(st[k]==st[i])
		ok=0;*/
return ok;
}

int succesor(int k)
{
	int ok=1;
	  if (st[k]<2)
          st[k]++;
	  else
		  ok=0;
	return ok;
}

void back(int k)
{
if(solutie(k))
{
      tipar(k);
      init(stc);
      back2(1);
}

else
  while(succesor(k))
  {
      //  if(valid(k))
		{
			st[k+1]=0;
		   back(k+1);

		}
  }

}


int main()
{
    long csuma=0;
    // citirea //
    f.open("flip.in");
    f>>n>>m;

        for(i=1;i<=n;i++)
        {
         for(j=1;j<=m;j++)
         {
             f>>a[i][j];
         }
        }

    maxim=0;
    back(1);
    //back2(1);


    g.open("flip.out");
    g<<maxim;


}