Cod sursa(job #65453)

Utilizator nobodybanAna Ban nobodyban Data 10 iunie 2007 00:34:11
Problema Jocul Flip Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <fstream>

using namespace std;

int n;
int m;

long a[17][17],b[17][17] ;

//long a[17][17];

void citire() {
	ifstream in("flip.in");
	in >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			in >> a[i][j];	
		a[i][m] = 1;
	}
	for (int j = 0; j < m; j++)
		a[n][j] = 1;
}

long suma(long a[17][17]) {
	long s = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) 
			if (a[n][j] * a[i][m] == 1){
				s += a[i][j];
			}
			else {
				s -= a[i][j];
			}

	return s;			
}

long suma_col(int c) {
	long s = 0;
	for (int i = 0; i < n; i++)
		if (a[i][m] == 1){
				s += a[i][c];
			}
			else {
				s -= a[i][c];
			}

	return s;			
}

void refac(long b[17][17], long a[17][17]) {
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <=  m; j++) 
			a[i][j] = b[i][j];
}

void fac() {
	for (int i = 0; i < n; i++)
		a[i][m] = 1;
	for (int i = 0; i < n; i++)
		a[n][i] = 1;
}

void schimba_linie (int l) {
	for (int i = 0; i < m; i++)
		a[l][i] = -a[l][i];
}

void schimba_coloana (int c) {
	for (int i = 0; i < n; i++)
		a[i][c] = -a[i][c];
}


//long actiune() {
//	long sm =  suma(a);
//	//refac(a, b);
//	long max = (1 << (n + m));
//	for (long x = 0; x < max; x++) {
//		long s = 0;
//		for (int i = 0; i < n; i++)
//			if  (x & (1 << i))
//			//	schimba_linie(i);
//				a[i][m] = -1;
//		for (int i = n; i < n + m; i++)
//			if  (x & (1 << i))
//			//	schimba_coloana(i - n);
//   		   	    a[n][i - n] = -1;
//		s = suma(a);
//		if (s > sm)
//			sm = s;
//		//refac(b, a);
//		fac();
//	}
//	return sm;
//}

long actiune(long a[17][17], int n, int m) {
	long sm =  suma(a);
	
	for (long x = 0; x < (1 << n); x++) {
		long s = 0;
		for (int i = 0; i < n; i++)
			if  (x & (1 << i))
				a[i][m] = -1;
		s = 0;
		for (int j = 0; j < m; j++) {
			int s1 = suma_col(j);
			if (s1 < 0)
   		   		a[n][j] = -1;			
		}
		s = suma(a);
		if (s > sm)
			sm = s;
		fac();
	}	
	return sm;
}

void transpusa () {
	for (int i = 0; i < m; i++) 
		for (int j = 0; j < n; j++)
			b[i][j] = a[j][i];
}

int main() {
	citire();
	ofstream out("flip.out");
	long s1 =  actiune(a, n, m);
	transpusa();
	long s2 =  actiune(b, m, n);
	out << (s1 > s2 ? s1 : s2); 
	out.close();
	return 0;
}