Cod sursa(job #65127)

Utilizator andrei.12Andrei Parvu andrei.12 Data 7 iunie 2007 10:14:14
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>
int n, m, a[17][17], s, smax, sol[17], col[17], lin[17], si, sc;
void prelucreaza(){
	int i, j;
	s=si;
	for (i=1;i<=m;i++)
		if (sol[i]==1) s-=2*col[i];
	if (s>smax) smax=s;
	sc=s;
	for (i=1;i<=n;i++){
		s-=2*lin[i];
		for (j=1;j<=m;j++)
			if (sol[j]==1)
				s+=4*a[i][j];
		if (s>smax){
			smax=s;
			sc=s;
		}
		else s=sc; 
	}
}
void back(int k){
	if (k==m+1)
		prelucreaza();
	else{
		sol[k]=-1;
		while (sol[k]<1){
			sol[k]++;
			back(k+1);
		}
	}
}
int main()
{
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	int i, j;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			s+=a[i][j];
		}
	smax=s;
	si=s;
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
			col[i]+=a[j][i];
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			lin[i]+=a[i][j];
	back(1);
	printf("%d\n",smax);
	fclose(stdin);
	fclose(stdout);
	return 0;
}