POJ1222 熄灯问题

Posted on |

问题描述
一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。在矩阵角上的按钮改变3盏灯的状态；在矩阵边上的按钮改变4盏灯的状态；其他的按钮改变5盏灯的状态。
image

在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变。对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变。
![image](http://poj.org/images/1222_2.jpg）

请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道：

(1)第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，每个按钮最多只需要按下一次；

(2)各个按钮被按下的顺序对最终的结果没有影响；

(3)对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重复下去，可以熄灭第1、2、3、4行的全部灯。同样，按下第1、2、3、4、5列的按钮，可以熄灭前5列的灯。

输入数据

第一行是一个正整数N，表示需要解决的案例数。每个案例由5行组成，每一行包括6个数字。这些数字以空格隔开，可以是0或1。0表示灯的初始状态是熄灭的，1表示灯的初始状态是点亮的。

输出要求

对每个案例，首先输出一行，输出字符串“PUZZLE #m”，其中m是该案例的序号。接着按照该案例的输入格式输出5行，其中的1表示需要把对应的按钮按下，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

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

输出样例

1
2
3
4
5
6
7
8
9
10
11
12
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
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

思路

枚举第一行的按钮情况
第一行的按钮确定（状态A），则只有按下第二行的开关才能使第一行灯全熄灭
同理 第3,4,5行按钮状态也确定，对于第一行的按钮每种状态（A）判断能否使最后一行的灯是否全熄灭

找一个局部状态去枚举

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<bitset>
#define MAX 100
using namespace std;
int puzzle[6][8];
int press[6][8];
bool guess(){
	int c,r;
	for(int r=1;r<5;r++){//!!
		for(int c=1;c<7;c++){
			press[r+1][c]=(puzzle[r][c]+press[r][c]+press[r-1][c]+press[r][c-1]+press[r][c+1])%2;//!!
		}
	} 

	//看最后一行灯是否全熄灭
	for(int j=1;j<7;j++){
		if(puzzle[5][j]!=(press[4][j]+press[5][j-1]+press[5][j+1]+press[5][j])%2) {
		return false;//!!!
	
	}} 
	return true;
}
void enumerate(){
	int c;
	for(c=1;c<7;c++) press[1][c]=0;
	while(guess()!=true){
		press[1][1]++;
		c=1;
		while(press[1][c]>1){
			press[1][c]=0;
			c++;
			press[1][c]++;
		} 	
	}
}
int main(){
	int n;
//	freopen("25.txt","r",stdin);
	cin>>n;
	for(int i=1;i<7;i++) press[0][i]=0;
	for(int j=0;j<6;j++)  {
	press[j][0]= press[j][7]=0;
	//puzzle[j][0]= puzzle[j][7]=0;
	}
	for(int k=0;k<n;k++){
		for(int i=1;i<6;i++){
		for(int j=1;j<7;j++){
			cin>>puzzle[i][j];
		} }
		enumerate();
		cout<<"PUZZLE #"<<k+1<<endl;
		for(int i=1;i<6;i++){
			for(int j=1;j<7;j++)
			cout<<press[i][j]<<" ";
			cout<<endl; 		
		}		
	} 
}