1222:EXTENDED LIGHTS OUT
描述
In an extended version of the game Lights Out, is a puzzle with 5 rows of 6 buttons each (the actual puzzle has 5 rows of 5 buttons each). Each button has a light. When a button is pressed, that button and each of its (up to four) neighbors above, below, right and left, has the state of its light reversed. (If on, the light is turned off; if off, the light is turned on.) Buttons in the corners change the state of 3 buttons; buttons on an edge change the state of 4 buttons and other buttons change the state of 5. For example, if the buttons marked X on the left below were to be pressed,the display would change to the image on the right.
The aim of the game is, starting from any initial set of lights on in the display, to press buttons to get the display to a state where all lights are off. When adjacent buttons are pressed, the action of one button can undo the effect of another. For instance, in the display below, pressing buttons marked X in the left display results in the right display.Note that the buttons in row 2 column 3 and row 2 column 5 both change the state of the button in row 2 column 4,so that, in the end, its state is unchanged.
Note:
1. It does not matter what order the buttons are pressed.
2. If a button is pressed a second time, it exactly cancels the effect of the first press, so no button ever need be pressed more than once.
3. As illustrated in the second diagram, all the lights in the first row may be turned off, by pressing the corresponding buttons in the second row. By repeating this process in each row, all the lights in the first
four rows may be turned out. Similarly, by pressing buttons in columns 2, 3 ?, all lights in the first 5 columns may be turned off.
Write a program to solve the puzzle.
总时间限制:
1000ms
内存限制:
65536kB
输入
The first line of the input is a positive integer n which is the number of puzzles that follow. Each puzzle will be five lines, each of which has six 0抯 or 1抯 separated by one or more spaces. A 0 indicates that the light is off, while a 1 indicates that the light is on initially.
输出
For each puzzle, the output consists of a line with the string: "PUZZLE #m", where m is the index of the puzzle in the input file. Following that line, is a puzzle-like display (in the same format as the input) . In this case, 1's indicate buttons that must be pressed to solve the puzzle, while 0 indicate buttons, which are not pressed. There should be exactly one space between each 0 or 1 in the output puzzle-like display.
样例输入
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郭炜老师：详解：
https://blog.csdn.net/yanyanwenmeng/article/details/82832580
https://blog.csdn.net/NNNNNNNNNNNNY/article/details/51584247
#include<iostream>
#include<cstring>
using namespace std;
char oriLights[5];//原始灯矩阵
char lights[5];//变化中的灯的矩阵
char result[5];//开关的方案
int GetBit(char c,int i){ //取字符c的第i个比特 return ( c >> i) & 1;//c按2进制数值('1':0011 0001,'0':0011 0000)右移i位后 如果原第i位是1，结果输出1，是0，结果输出0。} void SetBit(char & c, int i, int v){ //将第i位改成v ,&c指引用c if(v){//若v为1 c |= (1 << i);//将第i位改成1}else c &= ~(1 << i);//将第i位改成0}void FlipBit(char & c, int i){c ^= (1 << i);//^异或 相等则为0，不等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;//i行j列灯的状态，值：0或1 cin >> s;//读入原始灯数据 SetBit(oriLights[i],j,s);// 把S放入原始灯矩阵的i行j列 也就相当于把oriLights数组中第i个字符的第j个比特位填为s}//枚举开关状态 for(int n = 0; n < 64; ++n){//第一行开关的状态，2^6=64种状态 int switchs = n;memcpy(lights,oriLights,sizeof(oriLights));//每次试新状态前，要将初始矩阵状态重新复制到变化矩阵中 for(int i = 0; i < 5; ++i ){result[i] = switchs;//存第i行开关状态 for(int j = 0; j < 6; ++j){//枚举第i行的每个开关 if(GetBit(switchs,j)){//若j为1表示灯开着 if(j>0)//若j不是第一个灯 FlipBit(lights[i],j-1);//翻转前一个灯状态 ，放在变化中矩阵里 FlipBit(lights[i],j);if(j < 5)//若j不是最后一个灯 FlipBit(lights[i],j+1); // 翻转后一个灯状态}}if( i < 4 )// 若不是最后一行 lights[i+1] ^= switchs;//若switchs为1，则翻转 switchs = lights[i]; }if(lights[4] == 0){//若最后一行全灭 ，则成功 OutputResult(t,result);break;}} } return 0;}