熄灯问题

1.有一个由按钮组成的矩阵, 其中每行有6个按钮, 共5行
2.每个按钮的位置上有一盏灯
3.当按下一个按钮后, 该按钮以及周围位置(上边, 下边, 左边, 右边)的灯都会改变状态
4.如果灯原来是点亮的, 就会被熄灭
5.如果灯原来是熄灭的, 则会被点亮
• 在矩阵角上的按钮改变3盏灯的状态
• 在矩阵边上的按钮改变4盏灯的状态
• 其他的按钮改变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
样例输出
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

#include <memory>
#include <iostream>
#include <cstring>
using namespace std;

int GetBit(char c,int i){
    return (c>>i) & 1;
}
void SetBit(char &c,int i,int v){
    if(v){
        c|=(1<<i);
    }
    else{
        c&=~(1<<i);
    }
}
void Flip(char &c,int i){
    c^=(1<<i);
}
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 argc, char const *argv[])
{
    char oriLights[5];
    char lights[5];
    char result[5];
    char switchs;
    int T;
    cin>>T;
    for(int t=1;t<=T;++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 n=0;n<64;++n){
            memcpy(lights,oriLights,sizeof(oriLights));
            switchs=n;
            for(int i=0;i<5;++i){
                result[i]=switchs;
                for(int j=0;j<6;++j){
                    if(GetBit(switchs,j)){
                        if(j>0){
                            Flip(lights[i],j-1);
                        }
                        Flip(lights[i],j);
                        if(j<5){
                            Flip(lights[i],j+1);
                        }
                    }
                }
                if(i<4){
                    lights[i+1]^=switchs;
                }
                switchs=lights[i];
            }
            if(lights[4]==0){
                OutputResult(t,result);
                break;
            }
        }
    }
    return 0;
}

推荐阅读更多精彩内容