yingbi.cpp

把硬币摆放成32×9的矩阵

/*

  把硬币摆放成32×9的矩阵，你可以随意翻转矩阵中的某些行和某些列，问正面朝上的硬币最多有多少枚？
  提示：（1）任意一行或一列，翻两次等于没有翻；
  （2）对于9列的任何一种翻转的情况，每一行翻与不翻相互独立。
*/
#include <stdio.h>
/*
#define UP -2
#define DOWN 1
*/
int row,col;//
int a[32][9];
int b[32][9];//放置最优方案
int currentupnum=0;
int bestupnum=0;
int upnum=0;

/**
初始化，-1表示反面，1表示正面
**/
void readdata(){//
	for(int i=0;i<32;i++)
		for(int j=0;j<9;j++)
			a[i][j]=-1;
	a[1][4]=1;
/*	a[10][2]=1;
	a[12][4]=1;
	a[3][7]=1;	
	a[24][6]=1;
	a[17][6]=1;
	a[13][2]=1;
	a[19][1]=1;
	a[23][7]=1;	
	a[29][6]=1;
	a[31][8]=1;*/
}
/**
按整列反转
**/
void reversecol(int m)
{
	for(int i=0;i<32;i++){
		a[i][m]*=-1;
	}
}

/**
按整行反转
**/
void reverserow(int m){
	
	for(int i=0;i<9;i++){
		a[m][i]*=-1;
	}
}

/**
翻列子树到底时，考虑各行，若一行中向上的数小于5则翻转该行，upnum记录每行中向上的个数
currentupnum记录此次反转完毕后向上的硬币个数，bestupnum记录历次反转最多的向上硬币个数
b数组用来保存这一最优解
**/		
void checkmax(){
	for(int i=0;i<32;i++){
		upnum=0;
		for(int j=0;j<9;j++)
			if(1==a[i][j])upnum++;

			if(upnum<=4)reverserow(i);
		currentupnum+=upnum;
	}
	if(bestupnum<currentupnum){
		bestupnum=currentupnum;
		for(int i=0;i<32;i++)
		for(int j=0;j<9;j++)
			b[i][j]=a[i][j];
	}
	
}

//穷举反转列的所有情况
void search(int m){//
	
	if(m>8)
		checkmax();
	else{
		reversecol(m);//翻第m列
		search(m+1);
		reversecol(m);//不翻第m列
	
	search(m+1);
	}
}

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


void main(){
	readdata();
	search(0);
	printresult();
	
}