Cod sursa(job #59067)

Utilizator C11H17NO3Mesc Alin C11H17NO3 Data 7 mai 2007 23:06:52
Problema Jocul Flip Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <stdio.h>
#define N 16
#define M 16
int b[N][M];
int n, m;

int sum()
{
	int s, i, j;

	for (s = 0, i = 0; i < n; ++i)
		for (j = 0; j < m; ++j)
			s += b[i][j];
	return s;
}

void printb()
{
	int i, j;
	for (i = 0; i < n; ++i) {
		for (j = 0; j < m; ++j)
			printf("%5d", b[i][j]);
		printf("\n");
	}
}

void flipr(int r)
{
	int i;
//	printf("Flipping row %d\n", r);
	for (i = 0; i < m; ++i)
		b[r][i] = -b[r][i];
//	printb();
}

void flipc(int c)
{
	int i;

//	printf("Flipping column %d\n", c);
	for (i = 0; i < n; ++i)
		b[i][c] = -b[i][c];
//	printb();
}

int flipcscore(int c)
{
	int s, sf, i;
	for (s = 0, sf = 0, i = 0; i < n; ++i) {
		s += b[i][c];
		sf += -b[i][c];
	}
	if (sf > s) return sf - s;
	return 0;
}

int fliprscore(int r)
{
	int s, sf, i;
	for (s = 0, sf = 0, i = 0; i < m; ++i) {
		s += b[r][i];
		sf += -b[r][i];
	}
	if (sf > s) return sf - s;
	return 0;
}

#include <stdlib.h>

int main(int argc, char *argv[])
{
	FILE *in, *out;
	int i, j, score, idx, s, max, mscore = -900000000, type, it;
	in = fopen("flip.in", "r");
	out = fopen("flip.out", "w");
	fscanf(in, "%d", &n);
	fscanf(in, "%d", &m);
	for (i = 0; i < n; ++i)
		for (j = 0; j < m; ++j) 
			fscanf(in, "%d", &b[i][j]);
	
	it = 0;
	do {
			max = 0;
			idx = 0;
			type = 0;

		for (i = 0; i < n; ++i) {
			score = fliprscore(i);
			if (score > max) { max = score; idx = i; }
		}

		for (j = 0; j < m; ++j) {
			score = flipcscore(j);
			if (score > max) { max = score; idx = j; type = 1; }
		}
		
		if (max > 0) {
			if (!type) flipr(idx);
			else flipc(idx);
		} else {
			flipr(random() % n);
			flipc(random() % m);
			flipr(random() % n);
			flipc(random() % m);
			flipr(random() % n);
			flipc(random() % m);
		}
	
		s = sum();
		if (s > mscore) mscore = s;
		++it;	
	} while (it < 2000);

	fprintf(out, "%d", mscore);

	fclose(in); fclose(out);
	return 0;
}