問(wèn)題描述
　　有一個(gè)由按鈕組成的矩陣，其中每行有6 個(gè)按鈕，共5 行。每個(gè)按鈕的位置上有一盞燈。
當(dāng)按下一個(gè)按鈕后，該按鈕以及周?chē)恢?上邊、下邊、左邊、右邊)的燈都會(huì)改變一次。即，
如果燈原來(lái)是點(diǎn)亮的，就會(huì)被熄滅；如果燈原來(lái)是熄滅的，則會(huì)被點(diǎn)亮。在矩陣角上的按鈕
改變3 盞燈的狀態(tài)；在矩陣邊上的按鈕改變4 盞燈的狀態(tài)；其他的按鈕改變5 盞燈的狀態(tài)。
在下圖8-1 中，左邊矩陣中用X 標(biāo)記的按鈕表示被按下，右邊的矩陣表示燈狀態(tài)的改變。
與一盞燈毗鄰的多個(gè)按鈕被按下時(shí)，一次操作會(huì)抵消另一次操作的結(jié)果。在圖8-2 中，第2
行第3、5 列的按鈕都被按下，因此第2 行、第4 列的燈的狀態(tài)就不改變。根據(jù)上面的規(guī)則，
我們知道：
1) 第 2 次按下同一個(gè)按鈕時(shí)，將抵消第1 次按下時(shí)所產(chǎn)生的結(jié)果。因此，每個(gè)按鈕最多
只需要按下一次。
2) 各個(gè)按鈕被按下的順序?qū)ψ罱K的結(jié)果沒(méi)有影響。
3) 對(duì)第 1 行中每盞點(diǎn)亮的燈，按下第2 行對(duì)應(yīng)的按鈕，就可以熄滅第1 行的全部燈。如
此重復(fù)下去，可以熄滅第1、2、3、4 行的全部燈。同樣，按下第1、2、3、4、5 列
的按鈕，可以熄滅前5 列的燈。

?

對(duì)矩陣中的每盞燈設(shè)置一個(gè)初始狀態(tài)。請(qǐng)你寫(xiě)一個(gè)程序，確定需要按下哪些按鈕，恰好
使得所有的燈都熄滅。

輸入數(shù)據(jù)
第一行是一個(gè)正整數(shù) N，表示需要解決的案例數(shù)。每個(gè)案例由5 行組成，每一行包括6
個(gè)數(shù)字。這些數(shù)字以空格隔開(kāi)，可以是0 或1。0 表示燈的初始狀態(tài)是熄滅的，1 表示燈的
初始狀態(tài)是點(diǎn)亮的。
輸出要求
對(duì)每個(gè)案例，首先輸出一行，輸出字符串“PUZZLE #m”，其中m 是該案例的序號(hào)。接
著按照該案例的輸入格式輸出5 行，其中的1 表示需要把對(duì)應(yīng)的按鈕按下，0 則表示不需要
按對(duì)應(yīng)的按鈕。每個(gè)數(shù)字以一個(gè)空格隔開(kāi)。
輸入樣例
2
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
0 0 1 0 1 0
1 0 1 0 1 1
0 0 1 0 1 1
1 0 1 1 0 0
0 1 0 1 0 0
輸出樣例
PUZZLE #1
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
PUZZLE #2
1 0 0 1 1 1
1 1 0 0 0 0
0 0 0 1 0 0
1 1 0 1 0 1
1 0 1 1 0 1

?

我的解題思路：

　　首先根據(jù)題目的提示我們可以知道，每行（列）的亮滅只需它下一行（列）的相應(yīng)的燈來(lái)控制。那么我們就可想想到，第一行靠第二行的控制來(lái)全滅，同理，第二、三、四行都可以全滅。但這是還有第五行怎么控制呢？沒(méi)辦法了。。。。就在這卡住了。腫么辦？枚舉！對(duì)了，就是枚舉！既然最后一行我們不可以控制，那么我們就可以枚舉第一行按燈的情況。按或不按，總共2^6次方種情況，不多，只要把第一行的按燈情況，確定了，那么后面的都好辦了。然后就遍歷第一行的每種按燈情況，看一下哪一種情況下，剛剛好第五行的燈也全滅，那么這個(gè)就是我們想要的情況了。

　　但是在具體程序的實(shí)現(xiàn)上，還有很多的技巧要注意的。首先，它是個(gè)5X6的矩陣，但是我卻用了6x7的矩陣，這樣在按邊上（5X6的邊）的燈的時(shí)候，我們也同樣適用是五個(gè)燈同時(shí)變了，這樣用一個(gè)函數(shù)就能實(shí)現(xiàn)，不用考慮兩種情況。最后輸出只把5X6矩陣輸出就好了。對(duì)于第一行的情況的遍歷，我用的是遞歸的方式來(lái)遍歷。因?yàn)榍岸螘r(shí)間剛剛好把遞歸（recursion）又學(xué)了一遍。使用遞歸來(lái)實(shí)現(xiàn)遍歷，屢試不爽啊！主要注意的是狀態(tài)的恢復(fù)，主要是遞歸退出時(shí)候的狀態(tài)恢復(fù)。其它的就沒(méi)有什么了。具體的看代碼吧。

//遍歷搜索空間的例子：熄燈問(wèn)題 #include <stdio.h> #include <stdlib.h>int puzzl[7][8],press[7][8]; //這有個(gè)技巧 int nCase; FILE *fp;void input_data() {int row,col;for (row = 1; row < 6; row++){for (col = 1; col < 7; col++){fscanf(fp,"%d",&puzzl[row][col]);}} }void print_press() {int row,col;for (row = 1; row < 6; row++){for (col = 1; col < 7; col++){printf("%d ",press[row][col]);}printf("\n");} }void do_press(int row,int col) {int j;for (j = -1; j < 2; j++){if (puzzl[row][col+j] == 1){puzzl[row][col+j] =0;}else{puzzl[row][col+j] = 1;}}for (j = -1; j < 2; j++){if (j == 0){continue;}if (puzzl[row+j][col] == 1){puzzl[row+j][col] = 0;}else{puzzl[row+j][col] = 1;}}press[row][col] ^= 1;}void deal_first_line(int col) //col 從1開(kāi)始 {int i,m,n,nFlag;if (col == 7){//此時(shí)，第一行的狀態(tài)已經(jīng)定了。for (m = 1; m < 5; m++){for (n = 1; n < 7; n++){if (puzzl[m][n] == 1){do_press(m+1,n);}}}nFlag = 1;for (i = 1; i < 7; i++){if (puzzl[5][i] == 1){nFlag = 0;break;}}if (nFlag){//最后一行全為零printf("PUZZLE #%d\n",nCase);print_press();return;}}else{for (i = 0; i < 2; i++) // two status {if (i == 1){do_press(1,col);}deal_first_line(col + 1);if (i == 1){do_press(1,col); //若狀態(tài)已改變，恢復(fù)狀態(tài)。因?yàn)橥粋€(gè)鍵按兩次就會(huì)恢復(fù)原始狀態(tài) }}} }int main() {int nTime;fp = fopen("in.txt","r");fscanf(fp,"%d",&nTime);nCase = 1;while (nCase <= nTime){memset(press,0,sizeof(press));memset(puzzl,0,sizeof(puzzl));input_data();deal_first_line(1);nCase++;} }
2013/4/24 22:01

?標(biāo)準(zhǔn)答案中的代碼很精簡(jiǎn)，但是我想不到。搜索的方法不只知道叫什么。。。

void enumate( ) {int c;bool success;for ( c = 1; c < 7; c++)press[1][c] = 0;while( guess() == false ) {press[1][1]++;c = 1;while ( press[1][c] > 1 ) {press[1][c] = 0;c++;press[1][c]++;} }

?當(dāng)然，我的判斷的那部分也寫(xiě)得太拙劣了。其實(shí)按后的燈光情況我們根本就不必去考慮。在枚舉出第一行的press狀態(tài)后，我們可以這樣來(lái)判斷，技巧很重要啊！

bool guess() {int row,col;for (row = 1; row <= 4; row++ ){for (col = 1; col <= 6; col){press[row+1][col] = (puzzl[row][col] + press[row-1][col] + press[row][col] +press[row][col+1] + press[row][col-1]) % 2;}}for (col = 1; col <= 6){if (puzzl[5][col] != (press[4][col] + press[5][col] + press[5][col-1] + press[5][press+1]) % 2 ){return false;}}return true; }
2013/4/25 20:42

?

轉(zhuǎn)載于:https://www.cnblogs.com/Jason-Damon/archive/2013/04/24/3041251.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的枚举--遍历搜索空间的例子：熄灯问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。