Cod sursa(job #12166)

Utilizator airineivAirinei Vasile airineiv Data 3 februarie 2007 00:40:54
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include "stdio.h"

int N, M;
int a[16][16];

void comuta(int i, int j)
{
	int row, col;
	for(row=0; row<N; row++)
		for(col=0; col<M; col++)
		{
			if(row==i)
				a[row][col] *= -1;
			if(col==j)
				a[row][col] *= -1;
		}
}
int suma(void)
{
	int row, col;
	int suma = 0;
	for(row=0; row<N; row++)
		for(col=0; col<M; col++)
		{
			suma += a[row][col];
		}
	return suma;
}
int suma_com(int i, int j)
{
	int row, col;
	int suma = 0;
	for(row=0; row<N; row++)
		for(col=0; col<M; col++)
		{
			if(row==i)
				a[row][col] *= -1;
			if(col==j)
				a[row][col] *= -1;
			suma += a[row][col];
			if(row==i)
				a[row][col] *= -1;
			if(col==j)
				a[row][col] *= -1;
		}
	return suma;
}
int main(void)
{
	FILE *fin, *fout;
	
	int i,j;
	int rows[256], cols[256], sume[256], coef[256];
	if((fin = fopen("flip.in", "r"))==NULL)
		return -1;
	if((fout = fopen("flip.out", "w"))==NULL)
		return -1;
	fscanf(fin, "%d %d", &N, &M);
	for(i=0; i<N; i++)
		for(j=0; j<M; j++)
			fscanf(fin, "%d", &a[i][j]);
	int k=0;
	for(i=0; i<N; i++)
	{
		for(j=0; j<M;j++)
		{
			sume[k] = suma_com(i, j);
			if(suma() < sume[k])
			{
				rows[k] = i;
				cols[k++] = j;
			}
		}
	}
	int max = sume[0];
	int p = 0;
	coef[0] = 0;
	for(int t=0; t<k; t++)
	{
		int s = t;
		while(rows[t] == rows[s] || cols[t] == cols[s])
		{
			if(max<sume[t])
			{
				max = sume[t];
				coef[p++] = t;
			}
			t++;
			if(t==k)
				break;
		}
		t--;
	}
	if(p==0)
		p=1;
	for(i=0; i<p; i++)
		comuta(rows[coef[i]], cols[coef[i]]);
	fprintf(fout, "%d\n", suma());
	fclose(fin);
	fclose(fout);
	return 0;
}