算法熄灯

① 算法入门(5)熄灯问题

参考该链接 和B站上的视频做一些简单的拓展。
题目描述:
有一个5行6列的按钮矩阵，矩阵中每一个位数余闹置都有一个灯和一个按钮。
当按下某个位置下按钮后该位置和该位置周围(上，下，左，右)的灯的状态都会改变依次。
如果该位置在矩阵边上只会改变周围3个位置灯的状态，如果在角上只会改变周围两个位置灯的状态。如下图所示(复制北大mooc上的图)：

解题思路：
首先这是一道比较复杂的枚举题目。首先要根据已知推测隐含的条件。
1.一个位置灯的状态不仅受该位置按钮的影响也受周围按钮的影响。
2.每一个位置的按钮状态只有0未操作和1操作两种状态。如果对同一个位置按钮操作两次，操作结果抵消。相当于未对该位置的按钮进行操作。因此对一个位置的按钮的操作只有两毁悄种状态。
3.一共有5*6=30个按钮如果我们枚举出对按钮操作的所有可能情况是否可以通过其操作后的结果去判断该情况是否可以让所有的灯全部熄灭。
4.如果上述3是准确的话是否还有其他方法去找让全部灯熄灭的方案。
5.在这里我们不妨这样薯罩考虑一下啊，1.首先第一行一共有6个按钮我们先对这六个按钮的操作进行假设一共能得到64个操作方案。通过这64个操作方案我们能够得到64个操作后的结果。这时候如果第一排还有灯没有熄灭，又因为我们已经对第一排的按钮执行过了相应的操作，这时候如果我们想关闭第一排的灯的话只能通过第二排的按钮进行操作。对第二排操作完成后，如果想要关闭第二排的灯只能通过第三排的按钮进行操作....一直到操作到第五排。如果在操作完第五排后所有灯熄灭了，那么这个方案就是可行的，如果第五排未关闭完，那么该方案不可行。
在5 我们需要两个操作:

② 关灯游戏的算法...

根据示例可以看出，点了一个开关，其本身及四周开关取反，游戏代码如下，至于如何全部清空，慢慢点吧

<pstyle="padding:0;margin:0"><inputtype="button"id="btn_0_0"value="0"onclick="change(0,0)"/><inputtype="button"id="btn_0_1"value="1"onclick="change(0,1)"/><inputtype="button"id="btn_0_2"value="1"onclick="change(0,2)"/><inputtype="button"id="btn_0_3"value="0"onclick="change(0,3)"/><inputtype="button"id="btn_0_4"value="1"onclick="change(0,4)"/><inputtype="button"id="btn_0_5"value="0"onclick="change(0,5)"/></p>
<pstyle="padding:0;margin:0"><inputtype="button"id="btn_1_0"value="1"onclick="change(1,0)"/><inputtype="button"id="btn_1_1"value="0"onclick="change(1,1)"/><inputtype="button"id="btn_1_2"value="0"onclick="change(1,2)"/><inputtype="button"id="btn_1_3"value="1"onclick="change(1,3)"/><inputtype="button"id="btn_1_4"value="1"onclick="change(1,4)"/><inputtype="button"id="btn_1_5"value="1"onclick="change(1,5)"/></p>
<pstyle="padding:0;margin:0"><inputtype="button"id="btn_2_0"value="0"onclick="change(2,0)"/><inputtype="button"id="btn_2_1"value="0"onclick="change(2,1)"/><inputtype="button"id="btn_2_2"value="1"onclick="change(2,2)"/><inputtype="button"id="btn_2_3"value="0"onclick="change(2,3)"/><inputtype="button"id="btn_2_4"value="0"onclick="change(2,4)"/><inputtype="button"id="btn_2_5"value="1"onclick="change(2,5)"/></p>
<pstyle="padding:0;margin:0"><inputtype="button"id="btn_3_0"value="1"onclick="change(3,0)"/><inputtype="button"id="btn_3_1"value="0"onclick="change(3,1)"/><inputtype="button"id="btn_3_2"value="0"onclick="change(3,2)"/><inputtype="button"id="btn_3_3"value="1"onclick="change(3,3)"/><inputtype="button"id="btn_3_4"value="0"onclick="change(3,4)"/><inputtype="button"id="btn_3_5"value="1"onclick="change(3,5)"/></p>
<pstyle="padding:0;margin:0"><inputtype="button"id="btn_4_0"value="0"onclick="change(4,0)"/><inputtype="button"id="btn_4_1"value="1"onclick="change(4,1)"/><inputtype="button"id="btn_4_2"value="1"onclick="change(4,2)"/><inputtype="button"id="btn_4_3"value="1"onclick="change(4,3)"/><inputtype="button"id="btn_4_4"value="0"onclick="change(4,4)"/><inputtype="button"id="btn_4_5"value="0"onclick="change(4,5)"/></p>
<scripttype="text/javascript"src="~/Js/jquery-1.8.2.min.js"></script>
<scripttype="text/javascript">
functionchange(i,j)
{
varthisval=$("#btn_"+i+"_"+j).val()=="1"?"0":"1";
$("#btn_"+i+"_"+j).val(thisval);
if($("#btn_"+(i-1)+"_"+j)){
varupval=$("#btn_"+(i-1)+"_"+j).val()=="1"?"0":"1";
$("#line"+(i-1)).find("input").eq(j).val(upval)
}
if($("#btn_"+(i+1)+"_"+j)){
vardownval=$("#btn_"+(i+1)+"_"+j).val()=="1"?"0":"1";
$("#line"+(i+1)).find("input").eq(j).val(downval)
}
if($("#btn_"+i+"_"+(j-1))){
varleftval=$("#btn_"+i+"_"+(j-1)).val()=="1"?"0":"1";
$("#btn_"+i+"_"+(j-1)).val(leftval)
}
if($("#btn_"+i+"_"+(j+1))){
varrightval=$("#btn_"+i+"_"+(j+1)).val()=="1"?"0":"1";
$("#btn_"+i+"_"+(j+1)).val(rightval)
}
}
</script>

③ C++问题 熄灯问题

用回朔法解

使用Answer[m][n]表示答案， Answer元素山启的取值为{0,1}
Matrix[m][n]表示原始矩阵。

按照行优先的顺序扩展答案，使用step记录当前答案规模。

每一次扩展后，检查当前规模的答案是否有效的，只需检查当前规模的即可。

如果是有效地可以进一步扩展。
否则，修改当前地答案。

重复这个过程，知道当前答案的规模达到问题的规模，就找到了一个合适的解。

pseudo code

while(true)
{
if( step == problem_size)
return;

if( step < 0)
{
// maybe error
// or no solution can be found. It should not occur in this case
}

检查状态是否有效;

if(有渣橘效)
{
扩展下一个位置的答案
step++;
}
else
{
//回朔
//如果在当前位置答案可以修改，则修改，答案规模不变

if(可以修改)
{
修改当前答案； //只有一种可能: 从0到1
}
else
{
//缩小答案规模，修改之前地答如唯团案
step--;
}
}
}

输出答案。