題目描述

總時間限制: 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

解題分析

如果對所有5 * 6個按鈕枚舉，一共有2^30中策略，枚舉空間太大，可以找到枚舉空間的一個狀態局部，在這道題中第一行就是一個狀態局部，對第一行的開關狀態進行枚舉，一共有64種開關狀態，在第一行按下之后，第一行的燈有些被熄滅了，有些還在亮著，對于那些亮著的等，再在第二行的對應列按下，將第一行的所有燈熄滅，然后第二行還有一些燈亮著，再在第三行進行相同操作，直到按下第5行的燈，這個時候，如果第五行的燈全部熄滅，那么所有燈就滅了，我們就找到了一個按開關的策略。

從這道題可以看出，在枚舉空間較大的時候，可以通過找到一個狀態局部，對狀態局部進行枚舉，進而其他狀態就確定下來，或者大幅度減少，這樣，枚舉空間就可以減少很多。

在這道題的實現過程中，使用char數組分別保存燈的狀態，按鈕按下策略，然后每個比特表示燈亮或者滅，按鈕按下或者不按下。在i行按鈕按下后，i+1行的燈的狀態可以用按位異或i行的按鈕策略直接得到。

解題代碼

#include

#include

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個比特設置為v

if(v){

c |= 1 << i;

}

else{

c &= ~(1 << i);

}

}

void FlipBit(char & c, int i){//將c的第i個比特翻轉

c ^= 1 << i;

}

void OutputResult( char result[]){

for(int i = 0; i < 5; i++){

for(int j = 0; j < 6; j++){

printf("%d", GetBit(result[i], j));

if(j < 5) printf(" ");

}

printf("\n");

}

}

int main(){

for(int i = 0; i < 5; i++){

for(int j = 0; j < 6; j++){

int a;

scanf("%d", &a);

SetBit(oriLights[i], j, a);

}

}

for(int i = 0; i < 64; i++){ //這是對第一行按下策略的嘗試，不同的比特組合對應不同的整數，這個方法叫做狀態壓縮

int switchs = i; //swiths 表示當前行的按下狀態

memcpy(lights, oriLights, sizeof(oriLights)); //將輸入燈的狀態復制到按下過程中燈的狀態lights數組中

for(int i = 0; i < 5; i++){

result[i] = switchs;

for(int j = 0; j < 6; j++){ //對第i行按下按鈕后燈的狀態進行改變

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 < 4)

lights[i + 1] ^= switchs;//改變下一行燈的狀態

switchs = lights[i]; //更新i+1行按下策略

}

if(lights[4] == 0){

OutputResult(result);

break;

}

}

return 0;

}

總結

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

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