[POJ 1222] EXTENDED LIGHTS OUT

题目

?id=1222

描述

给你一个5行6列的矩阵分别表示30个灯，矩阵map[i][j]为1表示灯亮着, 0表示灯没亮. 要求你输出解决方案. press[i][j]为1表示按一下，0表示不按。使得最后状态为所有灯都熄灭。

分析

高斯消元法(Gaussian elimination method)

=> 对于每个格子 map[i][j], 能影响他的格子为 (i-1, j), (i, j-1), (i+1, j), (i, j+1), 以及自身(i, j).

=> (press[i-1][j] + press[i][j-1] + press[i+1][j] + press[i][j+1] + press[i][j] + map[i][j]) & 1 = 0 // press[x][y] 表示 0: 不按; 1: 按下.

=> (press[i-1][j] + press[i][j-1] + press[i+1][j] + press[i][j+1] + press[i][j]) & 1 = map[i][j]

那么就可以为每个格子列出一个方程, 得到共 30 个方程的方程组, 进而用高斯消元法来解方程组.

// 先给格子编好号 1 -> 30 // 然后就可以压缩为一维 => 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

将涉及不到的格子的系数设为 0.

然后就是普通的高斯消元了.

，好想从现在开始抱着你，紧紧地抱着你，一直走到上帝面前。