这样的熄灯问题会不会面试？

这得老长时间了。。。

会面试……其实这个与其说是算法题还不如说是脑筋急转弯
比如一个m*n的矩阵
简单的想法就是2^(m*n) 遍历所有可能 但是复杂度太高
我们考虑这样的一个矩阵
11010
00100
01001
........
如果我不动第一排的灯，那我怎么能让第一排的第三个和第五个灯熄灭呢？我只能通过第二排的第三个灯和第五个灯。注意第二排我只能动第三个和第五个灯，动其他灯都会造成第一排的某个灯亮起。
这样矩阵变成了：
11111
01001
01100
........
对第三行做同样的操作：目的是灭掉第二行亮着的灯。只能操作第三行的1、3、4号灯。如此往复直到最后一行，如果最后一行操作完，也全灭了，那你就成功了……
于是问题变成了：第一行应该怎么操作。
这个就好办了，2^n遍历。然后进行刚才介绍的操作看最后一行能否全灭。总复杂度(2^n)*m*n。
那如果n特别大呢？比如5*100000？那当然按列操作了……所以总复杂度是(2^min(m,n))*m*n。如果m和n都特别大呢？面试不会问的，相信我……（其实是我也不知道有没有有效的算法了）

ccarter 发表于 2014-5-23 14:31
会面试……其实这个与其说是算法题还不如说是脑筋急转弯
比如一个m*n的矩阵
简单的想法就是2^(m*n) 遍历 ...

赞思路。这个面试的时候会要求把代码也写出来么

ccarter 发表于 2014-5-23 14:31
会面试……其实这个与其说是算法题还不如说是脑筋急转弯
比如一个m*n的矩阵
简单的想法就是2^(m*n) 遍历 ...

大神啊！我写出来要一个多小时。。。。

这个问题是经典算法题，早就被人研究透了。

复杂度就是mn(2^n)，我相信很难有更优的算法了。

事实上也可以用高斯消元法求一组解。

robinho364 发表于 2014-5-23 22:39
这个问题是经典算法题，早就被人研究透了。

复杂度就是mn(2^n)，我相信很难有更优的算法了。

嗯，我刚刚开始算法这类的训练，以前玩开发，用些小工具，活少简单，算法太难，懒得搞~

哦，对了。

如果你只要求输出一组解的话，高斯消元的确就是高效解法哈。

数字媒体技术 发表于 2014-5-23 22:43
嗯，我刚刚开始算法这类的训练，以前玩开发，用些小工具，活少简单，算法太难，懒得搞~

Hi，突然发现你看的是pku的课件？

pku讲的倒是很不错！