Cod sursa(job #94784)

Utilizator slayer4uVictor Popescu slayer4u Data 25 octombrie 2007 12:36:59
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
long m, x[20][20], n, ma, max, i, j, st[20];
void flipline(int j)
{
	for (int i = 1; i <= m; i ++)
		x[j][i] *= -1;
}
void flipcolumn(int i)
{
	for (int j = 1; j <= n; j ++)
		x[j][i] *= -1;
}
void back(int k)
{
	if (k == n+1)
	{
		for (int i = 1; i <= m; i++)
		{
			int sum = 0;
			for (int j = 1; j <= n; j++)
				sum += x[j][i];
			if (sum < (-1)*sum) flipcolumn(i);
		}
		int num = 0;
		for (i = 1; i <= n; i ++)
			for (j = 1; j <= m; j ++)
				num += x[i][j];

		max = max < num ? num : max;
	}
	else
		for (int c = 0; c <= 1; c ++)
		{
			st[k] = c;
			if (c == 1)
				flipline(k);
			back(k+1);
			if (c == 1)
				flipline(k);

		}
}
int main()
{
	freopen ("flip.in","rt",stdin);
	freopen ("flip.out","wt",stdout);

	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i ++)
		for (j = 1; j <= m; j ++)
			scanf("%ld", &x[i][j]);

	back(1);

	printf("%ld\n", max);

	return 0;
}