题目大意是给你一个5*6的矩阵,矩阵里每一个单元都有一个灯和一个开关,如果按下此开关,那么开关所在位置的那个灯和开关前后左右的灯的状态都会改变(即由亮到不亮或由不亮到亮)。给你一个初始的灯的状态,问怎样控制每一个开关使得所有的灯最后全部熄灭,保证解唯一
刚开始看时,感觉像搜索,但状态太多,有2^30,必然超时。但可以发现,每一开关的影响是受上下左右影响的,也就是说,如果我第一行的开关状态定下来的话,那么第二行的开关状态也就定下来了,以此类推到最高行,如果最后最高行和目标状态一样,那么就发现答案。解决开关中间要涉及到一些位运算,详细参考代码!这题也可以用高斯消元做。
1 |
|