UC知道关灯游戏的算法...
来源：百度知道 编辑：UC知道 时间：2024/06/08 20:45:15
有一个5*6的灯泡构成的矩阵，灯的开关规则是这样：当改变某盏灯的，状态时，这盏灯的上下左右相邻的灯的状态也随之改变。例如：
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
当按下2行3列的开关时，状态变为：
0 1 0 0 1 0
1 1 1 0 1 1
0 0 0 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0
游戏的目的是对于任意给定的亮灭初始态，通过一系列动作关闭所有的灯。
可以注意到的是：
1.矩阵的状态与按开关的顺序无关
2.如果某个开关按下了两次，那么就相当于取消了第一次的操作，也就是说没有开关需要按超过1次
现在问题是：对于给定的初始状态，求出需要按哪些开关来完成游戏
原题地址(英文):
http://acm.zju.edu.cn/show_problem.php?pid=1354
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
当按下2行3列的开关时，状态变为：
0 1 0 0 1 0
1 1 1 0 1 1
0 0 0 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0
游戏的目的是对于任意给定的亮灭初始态，通过一系列动作关闭所有的灯。
可以注意到的是：
1.矩阵的状态与按开关的顺序无关
2.如果某个开关按下了两次，那么就相当于取消了第一次的操作，也就是说没有开关需要按超过1次
现在问题是：对于给定的初始状态，求出需要按哪些开关来完成游戏
原题地址(英文):
http://acm.zju.edu.cn/show_problem.php?pid=1354
我以前做过一个,不过挺麻烦,判断边界与非边界,反正就是点击一个,四周都变化就对了,比方说是个a(5,5)的数组,点击a(2,2)的时候(下标以0开始),a(1,2),a(2,1),a(3,2),a(2,3)都变化,不过这样写有点复杂,不知道有什么更好的算法
根据示例可以看出，点了一个开关，其本身及四周开关取反，游戏代码如下，至于如何全部清空，慢慢点吧
<p style="padding:0;margin:0"><input type="button" id="btn_0_0" value="0" onclick="change(0,0)" /><input type="button" id="btn_0_1" value="1" onclick="change(0,1)" /><input type="button" id="btn_0_2" value="1" onclick="change(0,2)" /><input type="button" id="btn_0_3" value="0" onclick="change(0,3)" /><input type="button" id="btn_0_4" value="1" onclick="change(0,4)" /><input type="button"