d*k
发帖数: 207 | 1 原帖见
http://www.mitbbs.com/article_t/JobHunting/32529909.html
一个2D matrix,每个cell都是一个灯泡，0表示灭，1表示亮，当一个灯泡发生变化的
时候，他临近的灯泡都要变化，问给你一个board configuration，让你判断是否可以
通过亮灭使得所有的灯泡都熄灭。这个题面试的哥们说他是朋友问他的，他也没做出来
，让我和他一起做，看能做出来不。 结果是大体有了一个solution，但是不知道对不
对。
===================================
我的想法：假设临近指的是上下左右四个。矩阵是m*n的。
枚举第一行每个灯泡的情况（动或者不动），共2^n种可能。对于每一种可能，由于第
一行已经确定，可以根据第一行的状态确定第二行的状态，例如对于mat[0][i]，若为1
，则必须动mat[1][i]，否则必须不动mat[1][i]。这样第二行就确定了。随后依次确定
后面的每一行。总时间复杂度为可耻的m*n*2^n。
大家看有更好的办法吗？ |
a********m
发帖数: 15480 | |
A***o
发帖数: 358 | 3 是一个经典问题，名字忘了，有几种特殊收敛的情况，看过wiki上的animation，好像
就是愣算。
【在 d*k 的大作中提到】
: 原帖见
: http://www.mitbbs.com/article_t/JobHunting/32529909.html
: 一个2D matrix,每个cell都是一个灯泡，0表示灭，1表示亮，当一个灯泡发生变化的
: 时候，他临近的灯泡都要变化，问给你一个board configuration，让你判断是否可以
: 通过亮灭使得所有的灯泡都熄灭。这个题面试的哥们说他是朋友问他的，他也没做出来
: ，让我和他一起做，看能做出来不。 结果是大体有了一个solution，但是不知道对不
: 对。
: ===================================
: 我的想法：假设临近指的是上下左右四个。矩阵是m*n的。
: 枚举第一行每个灯泡的情况（动或者不动），共2^n种可能。对于每一种可能，由于第
|
r**a
发帖数: 31 | 4 你的方法实现起来简单，当m和n有一个很小时非常实用
更通用的做法是解一个线性方程组(mod 2意义下的)，一共有m*n个方程和m*n个未知数
，每个未知数表示这个灯泡是否需要变化，每个方程表示一个灯泡的情况。举例来说，
设2*2的灯泡的情况是
V00 V01
V10 V11
这里Vij取值为0或1，表示灯泡一开始亮或灭。有方程组
X00 + X01 + X10 = V00
X00 + X01 + X11 = V01
X00 + X10 + X11 = V10
X01 + X10 + X11 = V11
在mod 2意义下解这个方程组就可以了。用直接的高斯消元法，复杂度是O((m*n)^3)。
因为这里方程组的系数非常有规律，实际上好像有更快的做法。
【在 d*k 的大作中提到】
: 原帖见
: http://www.mitbbs.com/article_t/JobHunting/32529909.html
: 一个2D matrix,每个cell都是一个灯泡，0表示灭，1表示亮，当一个灯泡发生变化的
: 时候，他临近的灯泡都要变化，问给你一个board configuration，让你判断是否可以
: 通过亮灭使得所有的灯泡都熄灭。这个题面试的哥们说他是朋友问他的，他也没做出来
: ，让我和他一起做，看能做出来不。 结果是大体有了一个solution，但是不知道对不
: 对。
: ===================================
: 我的想法：假设临近指的是上下左右四个。矩阵是m*n的。
: 枚举第一行每个灯泡的情况（动或者不动），共2^n种可能。对于每一种可能，由于第
|
l*n
发帖数: 529 | 5 你这已经是通行的heuristic解法了。
http://www.hamusutaa.com/pilot/solution.html
http://lbv-pc.blogspot.com/2012/08/turn-lights-off.html
就是第一行按或者不按，然后通过下面一行改上面一行。第一行2^n次方后还不行就是
不行了。
【在 d*k 的大作中提到】
: 原帖见
: http://www.mitbbs.com/article_t/JobHunting/32529909.html
: 一个2D matrix,每个cell都是一个灯泡，0表示灭，1表示亮，当一个灯泡发生变化的
: 时候，他临近的灯泡都要变化，问给你一个board configuration，让你判断是否可以
: 通过亮灭使得所有的灯泡都熄灭。这个题面试的哥们说他是朋友问他的，他也没做出来
: ，让我和他一起做，看能做出来不。 结果是大体有了一个solution，但是不知道对不
: 对。
: ===================================
: 我的想法：假设临近指的是上下左右四个。矩阵是m*n的。
: 枚举第一行每个灯泡的情况（动或者不动），共2^n种可能。对于每一种可能，由于第
|
