題目

總時間限制:
1000ms
內存限制:
65536kB

描述

有一個由按鈕組成的矩陣，其中每行有6個按鈕，共5行。每個按鈕的位置上有一盞燈。當按下一個按鈕后，該按鈕以及周圍位置(上邊、下邊、左邊、右邊)的燈都會改變一次。即，如果燈原來是點亮的，就會被熄滅；如果燈原來是熄滅的，則會被點亮。在矩陣角上的按鈕改變3盞燈的狀態；在矩陣邊上的按鈕改變4盞燈的狀態；其他的按鈕改變5盞燈的狀態。

在上圖中，左邊矩陣中用X標記的按鈕表示被按下，右邊的矩陣表示燈狀態的改變。對矩陣中的每盞燈設置一個初始狀態。請你按按鈕，直至每一盞等都熄滅。與一盞燈毗鄰的多個按鈕被按下時，一個操作會抵消另一次操作的結果。在下圖中，第2行第3、5列的按鈕都被按下，因此第2行、第4列的燈的狀態就不改變。

請你寫一個程序，確定需要按下哪些按鈕，恰好使得所有的燈都熄滅。根據上面的規則，我們知道
1）第2次按下同一個按鈕時，將抵消第1次按下時所產生的結果。因此，每個按鈕最多只需要按下一次；
2）各個按鈕被按下的順序對最終的結果沒有影響；
3）對第1行中每盞點亮的燈，按下第2行對應的按鈕，就可以熄滅第1行的全部燈。如此重復下去，可以熄滅第1、2、3、4行的全部燈。同樣，按下第1、2、3、4、5列的按鈕，可以熄滅前5列的燈。

輸入

5行組成，每一行包括6個數字（0或1）。相鄰兩個數字之間用單個空格隔開。0表示燈的初始狀態是熄滅的，1表示燈的初始狀態是點亮的。

輸出

5行組成，每一行包括6個數字（0或1）。相鄰兩個數字之間用單個空格隔開。其中的1表示需要把對應的按鈕按下，0則表示不需要按對應的按鈕。

樣例輸入

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

樣例輸出

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
來源 1222

解題分析

每個按鈕最多只需要按下一次，第2次按下同一個按鈕時,將抵消第1次按下時所產生的結果 。

各個按鈕被按下的順序對最終的結果沒有影響，對第1行中每盞點亮的燈, 按下第2行對應的按鈕, 就可以熄滅第1行的全部燈，如此重復下去, 可以熄滅第1, 2, 3, 4行的全部燈

第一想法: 枚舉所有可能的按鈕(開關)狀態, 對每個狀態計算一下最后燈的情況, 看是否都熄滅。
每個按鈕有兩種狀態(按下或不按下)一共有30個開關, 那么狀態數是2³⁰, 太多, 會超時。

如何減少枚舉的狀態數目呢?

基本思路: 如果存在某個局部, 一旦這個局部的狀態被確定,那么剩余其他部分的狀態只能是確定的一種, 或者不多的n 種, 那么就只需枚舉這個局部的狀態即可

本題是否存在這樣的 “局部” 呢?
經過觀察, 發現第1行就是這樣的一個 “局部”，
因為第1行的各開關狀態確定的情況下,
這些開關作用過后, 將導致第1行某些燈是亮的, 某些燈是滅的，
要熄滅第1行某個亮著的燈(假設位于第i列), 那么唯一的辦法就是按下第2行第i列的開關(因為第1行的開關已經用過了, 而第3行及其后的開關不會影響到第1行)。

為了使第1行的燈全部熄滅, 第2行的合理開關狀態就是唯一的
第2行的開關起作用后，為了熄滅第2行的燈, 第3行的合理開關狀態就也是唯一的
以此類推, 最后一行的開關狀態也是唯一的。

只要第1行的狀態定下來, 記作A, 那么剩余行的情況就是確定唯一的了
推算出最后一行的開關狀態, 然后看看最后一行的開關起作用后,
最后一行的所有燈是否都熄滅:
如果是, 那么A就是一個解的狀態
如果不是, 那么A不是解的狀態, 第1行換個狀態重新試試

利用位運算可以大幅減少計算量，
只需枚舉第1行的狀態, 狀態數是2⁶= 64
枚舉第一列, 狀態數是2⁵ = 32

代碼分析

1.首先來看頭文件和全局變量：

#include <memory> #include <string> #include <cstring> #include <iostream> using namespace std; char orilights[5]; //最初燈矩陣，一個比特表示一盞燈 char lights[5]; //不停變化的燈矩陣 char result[5]; //結果開關矩陣

2.由于要用到位運算，可以先寫幾個跟位運算相關的函數：
（1）獲得c的第i位

int getbit(char c,int i) {return (c>>i)&1; }

將c右移i位之后與1相與，如果原來第i位是1則返回1，如果原來第i位是0則返回0。

（2）改變c的第i位

void setbit(char & c,int i,int v) {//將c的第i位設置為vif(v) c|=(1<<i);else c&=~(1<<i); }

（3）翻轉c的第i位

void flipbit(char & c,int i) {c^=(1<<i); }

3.最后輸出結果的函數：

void outputresult(int t,char result[]) { cout<<"PUZZLE #"<<t<<endl;for(int i=0;i<5;++i){for(int j=0;j<6;++j){cout<<getbit(result[i],j);if(j<5) cout<<" ";}cout<<endl;} }

4.最后是主函數：

int main () {int T;cin>>T;for(int t=1;t<=T;++t){memset(orilights,0,sizeof(orilights));for(int i=0;i<5;++i){//讀入最初燈狀態for(int j=0;j<6;++j){int s;cin>>s;setbit(orilights[i],j,s);}}for(int n=0;n<64;++n){ //遍歷首行開關的64種狀態int switchs=n; //第i行的開關狀態memcpy(lights,orilights,sizeof(orilights));for(int i=0;i<5;++i){result[i]=switchs;//第i行的開關方案for(int j=0;j<6;j++){if(getbit(switchs,j)){if(j>0){flipbit(lights[i],j-1);//改左燈}flipbit(lights[i],j);//改開關位置的燈if(j<5){flipbit(lights[i],j+1);//改右燈}}}if(i<5){lights[i+1]^=switchs;//改下一行的燈}switchs=lights[i];//第i+1行開關方案和第i行燈情況同}if(lights[4]==0){outputresult(t,result);break;}}}return 0; }

完整代碼

#include <memory> #include <string> #include <cstring> #include <iostream> using namespace std; char orilights[5];//最初燈矩陣，一個比特表示一盞燈 char lights[5];//不停變化的燈矩陣 char result[5];//結果開關矩陣 int getbit(char c,int i) {//獲得c的第i位return (c>>i)&1; } void setbit(char & c,int i,int v) {//改變c的第i位if(v){c|=(1<<i);}else{c&=~(1<<i);} } void flipbit(char & c,int i) {//翻轉c的第i位c^=(1<<i); } void outputresult(int t,char result[]) {//輸出結果cout<<"PUZZLE #"<<t<<endl;for(int i=0;i<5;++i){for(int j=0;j<6;++j){cout<<getbit(result[i],j);if(j<5){cout<<" ";}}cout<<endl;} } int main () {int T;cin>>T;for(int t=1;t<=T;++t){memset(orilights,0,sizeof(orilights));for(int i=0;i<5;++i){//讀入最初燈狀態for(int j=0;j<6;++j){int s;cin>>s;setbit(orilights[i],j,s);}}for(int n=0;n<64;++n){ //遍歷首行開關的64種狀態int switchs=n;//第i行的開關狀態memcpy(lights,orilights,sizeof(orilights));for(int i=0;i<5;++i){result[i]=switchs;//第i行的開關方案for(int j=0;j<6;j++){if(getbit(switchs,j)){if(j>0){flipbit(lights[i],j-1);//改左燈}flipbit(lights[i],j);//改開關位置的燈if(j<5){flipbit(lights[i],j+1);//改右燈}}}if(i<5){lights[i+1]^=switchs;//改下一行的燈}switchs=lights[i];//第i+1行開關方案和第i行燈情況同}if(lights[4]==0){outputresult(t,result);break;}}// for( int n = 0; n < 64; n ++ )}return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的百练2811:熄灯问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。