| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 14231 | Accepted: 8817 |
Description
Input
Output
Sample Input
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
Sample Output
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
Source
– 如果灯原来是点亮的, 就会被熄灭
– 如果灯原来是熄灭的, 则会被点亮
? 在矩阵角上的按钮改变3盏灯的状态
? 在矩阵边上的按钮改变4盏灯的状态
? 其他的按钮改变5盏灯的状态
? 与一盏灯毗邻的多个按钮被按下时,一个操作会抵消另一次操作的结果
? 给定矩阵中每盏灯的初始状态，求一种按按钮方案，使得所有的灯都熄灭
输入:
– 第一行是一个正整数N, 表示需要解决的案例数
– 每个案例由5行组成, 每一行包括6个数字
– 这些数字以空格隔开, 可以是0或1
– 0 表示灯的初始状态是熄灭的
– 1 表示灯的初始状态是点亮的
输出:
– 对每个案例, 首先输出一行,
输出字符串 “PUZZLE #m”, 其中m是该案例的序号
– 接着按照该案例的输入格式输出5行
? 1 表示需要把对应的按钮按下
? 0 表示不需要按对应的按钮
? 每个数字以一个空格隔开
思路：
如何减少内存：这题灯一共五行六列，char占一个字节也就是有8位，可以用一位表示一列，所以每一行用一个char字符就能保存一行灯或开关的状态了，开一个char[5]就能保存所有灯或开关的状态了。
如何减少枚举次数：不用每行每列都枚举一遍，可以只枚举第一行开关所有的情况，共有2的6次方=64种，第一行的开关确定，剩下每一行的开关也就确定了。原因是因为题目要求是每个灯都要熄灭，
如果第一行的开关按完后，只会影响第一行和第二行，假设第一行还有未熄灭的灯，那么第二行的开关肯定就是要熄灭第一行的灯，依次类推，所以我们只需要枚举第一行的情况，最后看看按照第一行开关的按法，第五行的灯是不是全熄灭了就行。
#include<iostream>
#include<string.h>
using namespace std;
char orilight[5];//记录原始灯的情况 ，一共五行，每行用一个char字符表示原始灯的状态
char changelight[5];//灯的变化情况
char result[5];//最终开关方案
int T;//测试案例个数
void setBit(char &c,int i,int v)//设置c的第i位为v
{
if(v)
{
c |= (1<<i);//设为1
}
else
c &= ~(1<<i);//设为0 ，~：取反
}
int getBit(char c,int i)//获得c的第i位
{
int t = (c>>i) & 1;//右移i位后和1与
return t;
}
void flipBit(char &c,int i)//对c的第i位取反
{
c ^= (1<<i);//翻转某一位：与1异或
}
int main()
{
cin >> T;
for(int x = 1;x<=T;++x)
{
//输入测试数据
for(int i = 0;i<5;++i)
for(int j = 0;j<6;++j)
{
int t;
cin >> t;
setBit(orilight[i],j,t);
}
for(int n = 0;n<64;++n)
{
memcpy(changelight,orilight,sizeof(orilight));//每测试一种情况前都需要先把原始灯复制到改变灯数组里，调试改变灯数组里的 情况
int switchs = n;
for(int i = 0;i<5;++i)
{
result[i] = switchs;
for(int j = 0;j<6;++j)
{
int r = getBit(switchs,j);
if(r)
{
if(j>0)
flipBit(changelight[i],j-1);
flipBit(changelight[i],j);
if(j<5)
flipBit(changelight[i],j+1);
}
}
if(i<4)//把i+1正下面那个灯取反
changelight[i+1] ^= result[i];
switchs = changelight[i];//下一行的开关等于这一行亮的灯
}
if(changelight[4]==0)//如果第五行灯全熄灭了，说明这次方案是正确的
{
cout << "PUZZLE #"<<x<<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;
}
break;
}
}
}
return 0;
}
原文：https://www.cnblogs.com/knmxx/p/10320447.html