[POJ 1222] EXTENDED LIGHTS OUT【高斯消元法】

  • 2018-02-08
  • 0
  • 0

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.
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.

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;
}

评论

还没有任何评论,你来说两句吧



新博客地址:
darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io


常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai