參考該鏈接和B站上的視頻做一些簡單的拓展掀淘。
題目描述:
有一個5行6列的按鈕矩陣冷溃，矩陣中每一個位置都有一個燈和一個按鈕虑稼。
當按下某個位置下按鈕后該位置和該位置周圍(上，下菠剩，左，右)的燈的狀態(tài)都會改變依次耻煤。
如果該位置在矩陣邊上只會改變周圍3個位置燈的狀態(tài)具壮，如果在角上只會改變周圍兩個位置燈的狀態(tài)。如下圖所示(復(fù)制北大mooc上的圖)：
問題：給定矩陣的初始狀態(tài)，求一種按鈕的方案能夠?qū)⒕仃囍兴械臒粝纭?br> 輸入：
一個5*6的矩陣代表著燈的初始狀態(tài)炮赦。（其中1表示燈亮著狀態(tài)怜跑，0表示表示燈熄滅狀態(tài)）
0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
結(jié)果：
將矩陣軸的按鈕按照以下方案進行操作能夠讓所有的燈熄滅。(其中 1表示按下該按鈕吠勘，0標注無須操作)
1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0
解題思路：
首先這是一道比較復(fù)雜的枚舉題目性芬。首先要根據(jù)已知推測隱含的條件峡眶。
1.一個位置燈的狀態(tài)不僅受該位置按鈕的影響也受周圍按鈕的影響。
2.每一個位置的按鈕狀態(tài)只有0未操作和1操作兩種狀態(tài)植锉。如果對同一個位置按鈕操作兩次辫樱，操作結(jié)果抵消。相當于未對該位置的按鈕進行操作汽煮。因此對一個位置的按鈕的操作只有兩種狀態(tài)搏熄。
3.一共有5*6=30個按鈕如果我們枚舉出對按鈕操作的所有可能情況是否可以通過其操作后的結(jié)果去判斷該情況是否可以讓所有的燈全部熄滅。
4.如果上述3是準確的話是否還有其他方法去找讓全部燈熄滅的方案暇赤。
5.在這里我們不妨這樣考慮一下啊心例，1.首先第一行一共有6個按鈕我們先對這六個按鈕的操作進行假設(shè)一共能得到64個操作方案。通過這64個操作方案我們能夠得到64個操作后的結(jié)果鞋囊。這時候如果第一排還有燈沒有熄滅止后，又因為我們已經(jīng)對第一排的按鈕執(zhí)行過了相應(yīng)的操作，這時候如果我們想關(guān)閉第一排的燈的話只能通過第二排的按鈕進行操作溜腐。對第二排操作完成后译株，如果想要關(guān)閉第二排的燈只能通過第三排的按鈕進行操作....一直到操作到第五排。如果在操作完第五排后所有燈熄滅了挺益，那么這個方案就是可行的歉糜，如果第五排未關(guān)閉完，那么該方案不可行望众。
在5 我們需要兩個操作:
- press[r+1][c]=(puzzle[r][c]+press[r][c]+press[r-1][c]+press[r][c-1]+press[r][c+1]) % 2(press是按鈕操作矩陣匪补，puzzle是初始狀態(tài)矩陣。這個式子的含義是:第r+1行第c列按鈕是否需要按下烂翰，根據(jù)該位置燈的初始狀態(tài)和該位置前邊夯缺，后邊，左右和右邊的按鈕對該位置的操作去判斷甘耿。換句話說也就是該位置的燈燈狀態(tài)由一個初始狀態(tài)和前左右踊兜，本身四個位置的按鈕對該位置燈的操作決定。因此我們需要先通過前左右和本身四個位置的按鈕對r行c列位置燈操作后的結(jié)果佳恬。然后如果計算出為1的話我們需要通過 press[r+1][c]關(guān)閉它捏境，為0的話不用管了。)
- if (press[5][c-1]+press[5][c]+press[5][c+1]+press[4][c])%2!=puzzle[5][c]（如果第五行c列的初始狀態(tài)和第五行c列周圍操作疊加操作不一樣殿怜，那么燈就不會完全被熄滅典蝌。如第五行c列燈為1,四個操作疊加狀態(tài)為(1+1+1+1)%2=0，則第五行第c列的燈未被關(guān)閉头谜。 ）
- emmmm骏掀。。。截驮。python代碼還沒寫出來笑陈。等等再放吧。
