以下是代码
#include<iostream>
#include<memory>
#include<string>
#include<cstring>
using namespace std;
//一个矩阵,一个点表示一盏灯,当按下这个按钮后这个点包括与其相邻的点的状态会被改变。
//输入一个矩阵表示现在的状态。
//输出一个矩阵表示要如何按按钮才能将灯全部熄灭
//全部枚举的话可能性太多,会超时,可以采用枚举局部的方法,当有个局部确定的时候,其他部分就只有一种或者n钟可能的情况
//第一行就是一个局部
//要熄灭第一行第i列的灯,唯一的办法就是按下第二行,第i列的开关(第三行及其后的开关不会影响到第1行
//以此类推,当一行的状态确定时,下一行的按法也是确定的
//如果最后一行的
char oriLights[5];
char Lights[5];
char Result[5];
int GetBit(char c, int i) //获取第i位的状态
{
return (c >> i) & 1;
}
void SetBit(char &c, int i, int v) //设置第i位的状态
{
if (v)
{
c |= (1 << i); //第i位设置为1,按位或运算
}
else {
c &= ~(1 << i); //第i位设置为1 ,然后取反,按位与运算
}
}
void FlipBit(char &c, int i) //改变第i位的状态
{
c ^= (i << i); //与1异或运算相当于取反
}
void OutputResult(int t, char result[]) //输出数组
{
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()
{
int T;
cin >> T;
for (int t = 1; t <= T; t++)
{
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 n = 0; n < 64; n++)
{
int switchs = n; //n对应的二进制表示按按钮的方法
for (int i = 0; i < 5; i++)
{
Result[i] = switchs;
for (int j = 0; j < 6; j++) //一行六列,循环六次
{
if (GetBit(switchs, j)) //获取第j列的值
{
if (j > 0)
{
FlipBit(Lights[i], j-1);
}
FlipBit(Lights[i], j);
if (j < 5)
{
FlipBit(Lights[i], j + 1);
}
switchs = Lights[i];
}
}
if (i < 4) //不是最后一行的话,也要改变下一行的状态
{
Lights[i + 1] ^= switchs; //取反
}
}
if (Lights[4] == 0) //判断按法是否符合预期结果
{
OutputResult(t, Result); //输出矩阵
break;
}
}
}
}
网友评论