Cod sursa(job #2232722)

Utilizator YenmaRosu Cristian Yenma Data 20 august 2018 18:54:29
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
//============================================================================
// Name        : JoculFlip.cpp
// Author      : Cristi Rosu
// Version     :
// Copyright   : All rights reserved to Cristi Rosu
// Description : Jocul Flip in C++, Ansi-style
//============================================================================

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");

int a[20][20], n, m, i, j;
int cod[40], sol;

void afisare(int v[20][20]){
	for(i=1; i<=n; i++){
		for(j=1; j<=m; j++)
			g<<v[i][j]<<" ";
		g<<endl;
	}
}

int suma_matrice(int v[20][20]){
	int suma=0;
	for(i=1; i<=n; i++)
		for(j=1; j<=m; j++)
			suma+=a[i][j];
	return suma;
}

int valid(int k){
	int suma=0;
	if(cod[k]<=m){
		for(i=1; i<=n; i++)
			suma+=a[i][cod[k]];
		if(suma*(-1)>suma)
			return 1;
	}else{
		for(j=1; j<=m; j++)
			suma+=a[cod[k]-m][j];
		if(suma*(-1)>suma)
			return 1;
	}
	return 0;
}

void backtrack(int k){
	int temp=0;
	for(int t=1; t<=n+m; t++){
		cod[k]=t;
		if(valid(k)){
			if(cod[k]<=m)
				for(i=1; i<=n; i++)
					a[i][cod[k]]*=(-1);
			else
				for(j=1; j<=m; j++)
					a[cod[k]-m][j]*=(-1);
			temp=suma_matrice(a);
			if(temp>sol){
				sol=temp;
			}
			else
				backtrack(k+1);
		}
	}
}

int main() {
	f>>n>>m;
	for(i=1; i<=n; i++)
		for(j=1; j<=m; j++){
			f>>a[i][j];
		}
	sol=suma_matrice(a);
	backtrack(1);
	g<<sol;
	return 0;
}