Cod sursa(job #80156)

Utilizator coderninuHasna Robert coderninu Data 26 august 2007 16:51:53
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <stdio.h>
#define infile "flip.in"
#define outfile "flip.out"
#define nmax 17

long v[nmax][nmax], rez, linii[nmax], coloane[nmax];
int i, j, n, m, orien, pos;

void readdata();
void writedata();
void solve();

int search();

int main()
{
 readdata();
 solve();
 writedata();
 return 0;
}

void readdata()
{
 freopen(infile, "r", stdin);
 scanf("%d %d\n", &n, &m);
 for (i=1; i<=n; i++)
     for (j=1; j<=m; j++)
	 {
	  scanf("%ld ", &v[i][j]);
	  linii[i]+=v[i][j];
	  coloane[j]+=v[i][j];
	 }
 fclose(stdin);
}

void writedata()
{
 freopen(outfile, "w", stdout);
 printf("%ld\n", rez);
 fclose(stdout);
}

void solve()
{
 int gata=0;
 while (!gata)
     {
      gata=1;
      if (search())
	  {
	   gata=0;
	   if (!orien)
	       {
		for (i=1; i<=m; i++)
		    {
		     v[pos][i]=-v[pos][i];
		     coloane[i]+=2*v[pos][i];
		    }
		linii[pos]=-linii[pos];
	       }
	   else
	       {
		for (i=1; i<=n; i++)
		    {
		     v[i][pos]=-v[i][pos];
		     linii[i]+=2*v[i][pos];
		    }
		coloane[pos]=-coloane[pos];
	       }
	  }
     }
 for (i=1; i<=n; i++) rez+=linii[i];
}

int search()
{
 long min=2000000000;
 for (i=1; i<=n; i++)
     if (linii[i]<min)
	 {
	  min=linii[i];
	  pos=i;
	  orien=0;
	 }
 for (i=1; i<=m; i++)
     if (coloane[i]<min)
	 {
	  min=coloane[i];
	  pos=i;
	  orien=1;
	 }
 return min<0;
}