讯享网

输入

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

输出

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

以上就是熄灯问题的内容，接下来我们来分析

一、分析问题

1、简单分析

由各个按钮对灯的影响可知：

a、一个按钮最多只需要按一次

b、按下按钮的顺序对结果不会有影响

2、深入分析

通过按钮的影响以及灯的排列方式，我们可以简单的给出两个办法：

a、

暴力法，枚举，2 的 30 次方 是很大的一个数，如此的话这个程序对时间与空间的使用都是极大的，所以不使用这个方法（因为特别容易超时）

b、

第2个方法是，在第 i 行 的灯可以由  第 i + 1 行的按钮来熄灭 （i<5)

比如，第 1 行的 灯的状态是                                                                                                                                                                      0 1 0 1 1 0   

那么我们第 2 行的按钮就根据第一行的灯的状态来操作，即 第 2 行的按钮的操作为                                                                                0 1 0 1 1 0                                                                                   （1为按下按钮，0不按下按钮）（注意！！！就是说第 i+1 行的操作结果等于 第 i 行的灯的状态！记住且理解这个！待会要考）（如果无法理解接受可以自己在草稿纸上演练一遍，前面有例子）（最好自己在草稿纸上演练一遍加以理解）

这样第 1 行的灯就全熄灭了，然后第 2 行的灯接着由第 3 行的按钮来熄灭

但是问题来了，最后一行的灯如何熄灭？

我们只有5行的灯，前面 4 行都由它们的 i+1 行来熄灭，而第 5 行却没有它的 i+1 行帮它熄灭，所以第 5 行，也就是最后一行只能靠自己，也就是说 第 5 行不仅要熄灭第 4 行的灯，同时还要在熄灭第 4 行的灯的同时，也要恰好能熄灭自己第 5 行的灯

为了第 5 行的灯能恰好熄灭，所以我们就要枚举第 1 行的灯在进行了怎样的操作之后，能够在后续 i+1 行的操作下，使第 5 行的灯能恰好熄灭

比如，我第 1 行的操作是 0 0 0 0 0 0 的情况下，后续操作能够使最后一行灯恰好熄灭（即不操作最后一行也能熄灭）

或者如果不行，那么枚举下一种情况，即我第 1 行的操作是 0 0 0 0 0 1 的情况下，后续操作能够使最后一行灯恰好熄灭（即我按了一次第 1 行第 6 列的那妞，然后最后一行恰好熄灭）

如果不行则继续枚举下去

枚举的长度为 2的6次方  64     可以接受，不容易超时

分析完毕，接下来，我们开始设计算法

二、设计算法

1、输入值的保存

对于灯的状态值的保存我们直接就能想到用整型数组来保存，

但是我们再看一下输入样例和输出样例，它们的数值都只涉及到 1、0，就是说在整个运算过程中我们的运算只需要能处理 1、0 即二进制运算即可  

二进制对应的计算也就是位运算，为了方便位运算，所以我们不用整型数组保存，而采用 char 类型数组来保存

因为 char 类型由一个字节8位长度，所以保存一行6个灯的状态的存储空间就足够了

（先记住这个，如何保存我们一会儿再说。因为这个不是算法的核心，然后忘了位运算的话可以百度一下，很容易就想起来的）

2、写下完整代码

#include<iostream> #include<cstring> using namespace std; int getBit(char c,int i) // 取得c的第i比特位 { return (c>>i) & 1; } void setBit(char & c,int i,int v) // 这个函数主要用于保存输入的灯的状态 { if( v ) c |= 1<<i; else c &= ~(1<<i); } void Filp(char & c,int i) // 这个函数用于反转灯的状态 即 0 变 1 ，1 变 0 { c ^= 1<<i; } void OutputResult(char result[],int t) //输出结果 { cout<<"PUZZLE #"<<t<<endl; for(int i=0; i<5; ++i) { for(int j=0; j<6; ++j) { cout<<getBit(result[i],j); if(j<5) cout<<" "; } cout<<endl; } } int main() { char oriLights[5]; // 用于保存灯的原始状态 char lights[5]; // 这个是在枚举操作状态过程中用来变化枚举的灯的状态 char result[5]; // 用来保存结果 char switchs; // 用来枚举第一行的灯的操作 int n; cin>>n; for(int t=1; t<=n; ++t) { memset(oriLights,0,sizeof(oriLights)); // 初始化数组 for(int i=0; i<5; ++i) // 将原始灯的状态保存 { for(int j=0; j<6; ++j) { int s; cin>>s; setBit(oriLights[i],j,s); } } for(int i=0; i<64; ++i) // 用来枚举结果 { switchs = i; // 这是第 1 行的操作 memcpy(lights,oriLights,sizeof(oriLights)); // 不使用strcpy的原因是 str是字符串的拷贝，mem是字节拷贝，无限制数据类型 str总会拷贝‘\0’，有溢出风险 for(int j=0; j<5; j++) // 遍历每一行 { result[j] = switchs; // 将操作结果保存 for(int k=0; k<6; k++) // 遍历每一位 { if( getBit(switchs,k)){ // 返回为 1 则需要操作，即改变所影响到的灯的状态 if(k>0) // 改左边 Filp(lights[j],k-1); Filp(lights[j],k); // 改自己 if(k<5) Filp(lights[j],k+1); // 改右边 } } if(j<4) // 改下一行的收到操作影响的灯的状态 lights[j+1] ^= switchs; switchs = lights[j]; // 考点： i 行的灯的状态等于 i+1 行的操作 } if(lights[4] == 0) 判断最后一行的灯的状态是否是全部熄灭 { OutputResult(result,t); break; } } } // for(int k=0; k<n; ++k) return 0; }

大致就是如此了，如有不懂，可评论