Cod sursa(job #731707)

Utilizator Alexxino7Alexandru Popescu Alexxino7 Data 8 aprilie 2012 22:30:55
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream>
using namespace std;

ifstream fin("flip.in");
ofstream fout("flip.out");

long long N,M,Flip[20][20],maxsum,UsedLine[20],UsedColumn[20];

void getsum(){
	int sumaux=0;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			sumaux+=Flip[i][j];
		}
	}
	if(sumaux>maxsum)
		maxsum=sumaux;
}

void changeline(int i){
	for(int j=1;j<=M;j++){
		Flip[i][j]*=-1;
	}
}

void undoline(int i){
	for(int j=1;j<=M;j++){
		Flip[i][j]*=-1;
	}
}

void changecolumn(int j){
	for(int i=1;i<=N;i++){
		Flip[i][j]*=-1;
	}
}

void undocolumn(int j){
	for(int i=1;i<=N;i++){
		Flip[i][j]*=-1;
	}
}

void back(int k,int i,int j){
	if(k==N+M+1)
		;
	else{
		for(;i<=N && !UsedLine[i];){
			UsedLine[i]=1;
			changeline(i);
			getsum();
			back(k+1,i+1,j);
			for(;j<=M && !UsedColumn[j];){
				UsedColumn[j]=1;
				changecolumn(j);
				getsum();
				back(k+1,i,j+1);
				UsedColumn[j]=0;
				undocolumn(j);
			}
			UsedLine[i]=0;
			undoline(i);
		}
	}
}

int main(){
	fin>>N>>M;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			fin>>Flip[i][j],maxsum+=Flip[i][j];
		}
	}
	back(1,1,1);
	fout<<maxsum<<"\n";
	fin.close();
	fout.close();
	return 0;
}