演算法熄燈

① 演算法入門(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--;
}
}
}

輸出答案。