【acm暴力枚举】熄灯问题

题目描述

这是个很好的题目！今天写到这道题感觉很有意思，不论从思路还是代码上，都需要总结。

有一个5*6的矩阵，每个位置上都有一盏灯和一个按钮，每按一次按钮，这盏灯及周围四个相邻位置的灯都会改变一次，如图：

请写一个程序，输入T组数据，每组数据中输入一个0 1矩阵，输出一个矩阵，表示出哪些按钮是需要操作的？恰好使得所有灯都熄灭！

题解

这题乍一看蛮玄的，细细分析还是发现有规律可循…

从第一行往下看，如果有灯开着，那么我们需要按它对应的下一行按钮，以此类推，某一行有灯亮着，按下一行对应位置按钮…那么就类推到了最后一行，现在就需要判断最后一行是否都熄灭了…

为了处理二维数组比较方便，建二维数组的时候扩充到边缘，让存储值的区域下标从1开始比较好

代码

#include<iostream>
using namespace std;
int puzzle[6][8],press[6][8];
//对状态进行判断 
bool guess(void){
	int i,j;
	//下一行的对应位置该怎么操作？ 
	for(i=1;i<5;i++){
		for(j=1;j<7;j++){
			press[i+1][j]=(puzzle[i][j]+press[i][j]+press[i-1][j]+press[i][j-1]+press[i][j+1])%2;			
		}
	}
	//判断最后一行熄灭了吗？
	for(j=1;j<7;j++){
		if((press[5][j-1]+press[5][j]+press[5][j+1]+press[4][j])%2!=puzzle[5][j]) return false;
	} 
	return true;
}
//枚举第一行的各种情况 
void enumate(void){
	int j;
	for(j=1;j<7;j++){
		press[1][j]=0;
	}
	while(guess()==false){//如果最后一行没熄灭才执行下一项枚举，最后一行都熄灭了就在main直接打印press 
		//这里枚举每一位0 1值很重要 有2^6中情况
		press[1][1]++;
		j=1;
		while(press[1][j]>1){
			press[1][j]=0;
			j++;
			press[1][j]++;
		}
	}
}

int main(){
	int T,t,i,j;
	cin>>T; 
	//清零左右边栏
	for(i=0;i<6;i++) press[i][0]=press[i][7]=0;
	//清空上边栏
	for(j=1;j<7;j++) press[0][j]=0;
	for(t=1;t<=T;t++){
		//读入puzzle数组
		for(i=1;i<6;i++){
			for(j=1;j<7;j++){
				cin>>puzzle[i][j];
			}
		}
		enumate();
		cout<<"PUZZLE #"<<t<<endl;
		//打印press数组
		for(i=1;i<6;i++){
			for(j=1;j<7;j++){
				cout<<press[i][j]<<" ";
			}
			cout<<endl;
		}		
	}
	return 0;
}
           

样例输出

2
0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0
PUZZLE #1
1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0
//这里其实没有换行哦
0 0 1 0 1 0
1 0 1 0 1 1
0 0 1 0 1 1
1 0 1 1 0 0
0 1 0 1 0 0
PUZZLE #2
1 0 0 1 1 1
1 1 0 0 0 0
0 0 0 1 0 0
1 1 0 1 0 1
1 0 1 1 0 1

--------------------------------