[POJ 1222] EXTENDED LIGHTS OUT【高斯消元法】
Problem:
| Time Limit: 1000MS | Memory Limit: 10000K |
Description
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.
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.
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.
Input
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.
Output
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.
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
Greater New York 2002
Solution:
# 今天晚上开始放寒假啦啦啦啦啦啦啦~~~ #
本题可以巧妙地构造异或方程组，采用高斯消元法求解。
我们可以将 5 × 6 = 30 个开关作为未知数 x1 ~ x30。
由于同一个开关按两下等于没按，我们不妨假设 xi 的取值只能为 0 或 1。
我们可以将某盏灯的初始状态表示为对其有影响的开关按下情况的异或值，构造出 30 个方程。
只需要存该异或方程组的增广矩阵，跑一遍高斯消元即可求出一组解。
Code: O(Tn3) [356K, 0MS]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int T, pz[10][10];
int mat[35][35], ans[35];
inline void Gauss_xor(){
for(register int i = 1; i <= 30; i++){
int major;
for(major = i; major <= 30; major++)
if(mat[major][i]) break;
for(register int j = i; j <= 31; j++) swap(mat[major][j], mat[i][j]);
for(register int j = i + 1; j <= 30; j++)
if(mat[j][i])
for(register int k = i; k <= 31; k++)
mat[j][k] ^= mat[i][k];
}
for(register int i = 30; i >= 1; i--){
ans[i] = mat[i][31];
for(register int j = i + 1; j <= 30; j++)
if(mat[i][j]) ans[i] ^= ans[j];
}
}
int main(){
scanf("%d", &T);
for(register int curT = 1; curT <= T; curT++){
for(register int i = 1; i <= 5; i++)
for(register int j = 1; j <= 6; j++)
scanf("%d", &pz[i][j]);
memset(mat, 0, sizeof(mat));
for(register int i = 1; i <= 5; i++)
for(register int j = 1; j <= 6; j++){
int sub = (i - 1) * 6 + j;
mat[sub][sub] = 1;
if(i > 1) mat[sub][sub - 6] = 1;
if(i < 5) mat[sub][sub + 6] = 1;
if(j > 1) mat[sub][sub - 1] = 1;
if(j < 6) mat[sub][sub + 1] = 1;
mat[sub][31] = pz[i][j];
}
Gauss_xor();
printf("PUZZLE #%d\n", curT);
for(register int i = 1; i <= 5; i++){
for(register int j = 1; j <= 6; j++){
if(j > 1) putchar(' ');
printf("%d", ans[(i - 1) * 6 + j]);
}
putchar('\n');
}
}
return 0;
}
发表评论