https://www.cnblogs.com/huashanqingzhu/p/7278930.html
http://bailian.openjudge.cn/practice/1222
1222:EXTENDED LIGHTS OUT
It took me a lot of time to figure out this question. The more difficult place to think about is the enumeration in the first line. Suppose The six elements in the first row are 0 1 0 1 0 1,
A light has only two states: on and off. There are only two operations for each lamp, pressing the switch and not pressing the switch, I thought the enumeration was 0~63, that is, 0000 0000 ~1111 1111,
This idea is wrong. Because the initial state of the light is certain, you may affect the surrounding lights if you press any one, so there may not be 1111 1111 in this state.
The key is to figure out what the enumeration status is? The enumeration is the operation of each lamp, 1 means pressing the switch, 0 means no operation,
The first line of this There are 2^6 possibilities for pressing the switch. As long as the operation of each lamp in the first line is determined, the state of the first line of light is determined, and then the second line lights up according to the first line The position of the lamp, switch the lamp operation
- Description
-
There is a matrix of buttons, in which there are 6 buttons in each row for a total of 5 rows. There is a light at the location of each button. When a button is pressed, the button and the surrounding position (upper, lower, left, right) lights will change once. That is, if the lamp was originally lit, it will be extinguished; if the lamp was originally extinguished, it will be lit. The button on the corner of the matrix changes the state of 3 lights; the button on the side of the matrix changes the state of 4 lights; the other buttons change the state of 5 lights.
In the above figure, the button marked with an X in the left matrix indicates that it is pressed, and the right matrix indicates the change of the light state. Set an initial state for each lamp in the matrix. Please press the button until each lamp goes out. When multiple buttons adjacent to a light are pressed, one operation will cancel out the result of another operation. In the following figure, the buttons in the 3rd and 5th columns of the second row are all pressed, so the state of the lights in the second and fourth columns does not change.
Please write a program , To determine which buttons need to be pressed, just to make all the lights go out. According to the above rules, we know that 1) When the same button is pressed for the second time, the result produced by the first press will be offset. Therefore, each button only needs to be pressed once at most; 2) The order in which the buttons are pressed has no effect on the final result; 3) For each light in the first row, press the corresponding button in the second row , You can turn off all the lights in the first row. Repeat this procedure to turn off all the lights in rows 1, 2, 3, and 4. Similarly, press the buttons in columns 1, 2, 3, 4, and 5 to turn off the lights in the first 5 columns.
Enter
It consists of 5 lines, and each line contains 6 numbers (0 or 1). Use a single space to separate two adjacent numbers. 0 means that the initial state of the light is off, and 1 means that the initial state of the light is on.
Output
It consists of 5 lines, each line includes 6 numbers (0 or 1). Use a single space to separate two adjacent numbers. Among them, 1 means that the corresponding button needs to be pressed, and 0 means that the corresponding button does not need to be pressed.
Sample input
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
Sample output
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
Problem solving analysis
< span class="fontstyle0">Source: Teacher Guo Wei, Peking University
•Press When the same button is , it will cancel the result produced by the first press, so each button You only need to press it once at most.
•The order in which the buttons are pressed has no effect on the final result
• For each light in the first row, press the button corresponding to the second row to turn off all the lights in the first row
• Repeat this way, you can turn off all the lights in rows 1, 2, 3, and 4
First thought:
Enumerate all possible button (switch) states, for each state, calculate the last light situation, and see if they are all off.
Each button has two states (pressed or not), There are a total of 30 switches, so the number of states is 230, if there are too many, it will time out.
How to reduce the number of enumerated states?
Basic idea: If there is a part, once the part of the state is OK, then the remaining state of the other parts can only be a certain kind, or a few n kinds, then only this partial state needs to be enumerated.
Does this question exist? What about “partial”?
After observation, it was found that line 1It’s such a “partial”
Because the operation plan of each switch in line 1 is determined, after these switches are operated, some lights in line 1 will be on and some lights will be off.
To turn off a light on line 1 (assuming it is in the i-th column), then the only way is to press the i-th line in the second line Column switch. (Because the switch in line 1 has already been used, and the switches in line 3 and after will not affect the first line)
In order to make The lights in the first row are all off, and the reasonable switch operation scheme in the second row is the only one.
After the switch operation in line 2, in order to turn off the light in line 2, the reasonable switch operation scheme in line 3 is also the only one. and so on, the switch operation scheme of the last line is also unique.
As long as the operation plan of the first line is determined, denoted as A, then the operation plan of the remaining lines is determined and unique.
Calculate the switch operation plan of the last line, and then check whether all the lights in the last line are off after the switch operation of the last line:
If yes, Then A is a solution state; If it is not, then A is not a solution state, and try again with another state in the first line.
Only enumerate number 1 The operation plan of the row, the number of states is 2^6 = 64
span>
Is there a way to reduce the number of states?
Enumerate the first column, the number of states is 2^5 = 32
CodeSource: Peking University Teacher Guo Wei, here are only some supplements and amendments to the notes.
/*
http://bailian.openjudge.cn/practice/1222
1222:EXTENDED LIGHTS OUT
level: hard
*/
#include
#include
#include<string>
#include
using namespace std;
int GetBit(char c, int i) // get a certain Value
{
//get char c No.i Bit
return (c >> i) & 1;
}
void SetBit(char &c, int i, int v) // Turn a position into 0 or 1
{
//set char c No.i bit is v
if (v)
{
c |= (1 << i);
}
else
{
c &= ~(1 << i);
}
}
void Flip(char & c, int i) // flip a bit
{
//char c No. i bit flip
c ^= (1 << i);
}
void OutputResult(int t, char result[]) // output result< /span>
{
cout << "PAZZLE #" << 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]; // original input
char lights[5]; // Intermediate calculation result
char result[5]; // The last output switch operation, 1 represents the switch is pressed, 0 represents no operation
char switchs; // Switch information of a row
int T;
cin >> T;
for (int t = 1; t <= T; t++)
{
memset(oriLights, 0, sizeof(oriLights) ); // if not omit??
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++) //< /span>64 operations to traverse the first line of switches
{
memcpy(lights, oriLights, sizeof(oriLights));
switches = n; //First assume that the switch on line 0 needs Operation plan
for (int i = 0; i <5; ++i)
{
result[i] = switches;//Save the i-th line switch Operation plan
for (int j = 0; j <6; ++j)//Modify the lamp in line i according to the plan
{
if (GetBit(switchs, j)) //The j-th digit of switches equal to 1 means that the j-th button in the i-th row needs to be pressed, and 0 means that the button does not need to be pressed
{
if (j> 0)
Flip(lights[i], j - 1);// Change the left light
Flip(lights[i], j);//Change the switch position light< /span>
if (j <5)
Flip(lights[i], j + 1);// Change the right light
}
}
if (i <4)
lights[i + 1] ^= switchs;//Change the light of the next line
switchs = lights[i];//the operation scheme of the i+1 line switch Determined by the status of the i-th row light
}
if (lights[4] == 0)
{
OutputResult(t, result);
break;
}
}
}
return 0;
}
/*
http://bailian.openjudge.cn/practice/1222
1222:EXTENDED LIGHTS OUT
level: hard
*/
#include
#include
#include<string>
#include
using namespace std;
int GetBit(char c, int i) // get a certain Value
{
//get char c No.i Bit
return (c >> i) & 1;
}
void SetBit(char &c, int i, int v) // Turn a position into 0 or 1
{
//set char c No.i bit is v
if (v)
{
c |= (1 << i);
}
else
{
c &= ~(1 << i);
}
}
void Flip(char & c, int i) // flip a bit
{
//char c No. i bit flip
c ^= (1 << i);
}
void OutputResult(int t, char result[]) // output result< /span>
{
cout << "PAZZLE #" << 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]; // original input
char lights[5]; // Intermediate calculation result
char result[5]; // The last output switch operation, 1 represents the switch is pressed, 0 represents no operation
char switchs; // Switch information of a row
int T;
cin >> T;
for (int t = 1; t <= T; t++)
{
memset(oriLights, 0, sizeof(oriLights) ); // if not omit??
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++) //< /span>64 operations to traverse the first line of switches
{
memcpy(lights, oriLights, sizeof(oriLights));
switches = n; //First assume that the switch on line 0 needs Operation plan
for (int i = 0; i <5; ++i)
{
result[i] = switches;//Save the i-th line switch Operation plan
for (int j = 0; j <6; ++j)//Modify the lamp in line i according to the plan
{
if (GetBit(switchs, j)) //The j-th digit of switches equal to 1 means that the j-th button in the i-th row needs to be pressed, and 0 means that the button does not need to be pressed
{
if (j> 0)
Flip(lights[i], j - 1);// Change the left light
Flip(lights[i], j);//Change the switch position light< /span>
if (j <5)
Flip(lights[i], j + 1);// Change the right light
}
}
if (i <4)
lights[i + 1] ^= switchs;//Change the light of the next line
switchs = lights[i];//the operation scheme of the i+1 line switch Determined by the status of the i-th row light
}
if (lights[4] == 0)
{
OutputResult(t, result);
break;
}
}
}
return 0;
}