前言

本文中博主將一步一步地、以正常人的順序思維完成題目——費(fèi)解的開(kāi)關(guān)，使用的核心方法是遞推與遞歸。

題目

參考題目：費(fèi)解的開(kāi)關(guān)

詳細(xì)的題目信息相信大家都已經(jīng)知道了，因此這里為了簡(jiǎn)潔只展示輸入輸出格式及數(shù)據(jù)范圍。

(資料圖片僅供參考)

核心思維

本題利用遞推做的核心思想很簡(jiǎn)單，即當(dāng)這個(gè)5x5數(shù)組的第一行被處理完過(guò)后，想要開(kāi)啟第一行仍然滅著的燈，則必須點(diǎn)擊該燈的下一行的相同位置。

因此，只要確定好第一行如何選擇，其他行也自然確定了，之需要判斷該種情況是否滿足題目條件即可。

如圖所示：

假設(shè)我們第一行只點(diǎn)一次，即被藍(lán)色X的地方，點(diǎn)完后會(huì)變成這樣：

如果我們想讓第一行的第一個(gè)、第四個(gè)變亮，那么第二行的第一個(gè)、第四個(gè)就是必點(diǎn)的。

因此，我們只需要枚舉第一行的所有選法，然后就能遞推出整個(gè)四方體的選法，最后判斷成是否成立。

寫出數(shù)據(jù)輸入格式

首先，先在主函數(shù)里寫出題目要求的輸入格式。先輸入一個(gè)n，隨后進(jìn)行n次循環(huán)，每次循環(huán)都讀入25個(gè)數(shù)據(jù)放在一個(gè)二維數(shù)組arr里。為了傳參的時(shí)候方便，我們把二維數(shù)組放在外面，像這樣：

int arr[5][5];int main(){int n = 0;scanf("%d", &n);while (n--){int i = 0;for (i = 0; i < 5; i++){int j = 0;for (j = 0; j < 5; j++){scanf("%1d", &arr[i][j]);}}//...}return 0;}

注意：本題在Acwing上數(shù)據(jù)輸入時(shí)，每個(gè)數(shù)據(jù)之間沒(méi)有空格，因此要控制scanf每次讀取數(shù)據(jù)的寬度。代碼中的“//...”代表接下來(lái)從此處開(kāi)始寫。

枚舉第一行的選擇

這里我們使用遞歸的方法，即在1 ~ 5里面選出1 ~ 5個(gè)數(shù)，每一種選法都是一種第一行的選擇。創(chuàng)建遞歸函數(shù)dfs（int step），step代表當(dāng)前枚舉的位置，在外面創(chuàng)建數(shù)組choose代表遞歸時(shí)每個(gè)位置的狀態(tài)，每次枚舉當(dāng)前位置選或者不選，五個(gè)位置都枚舉結(jié)束后就代表形成了一種情況，隨后利用判斷函數(shù)jud對(duì)這種情況進(jìn)行判斷。

int main(){//...dfs(0);//dfs的位置}return 0;}

int arr[5][5];int choose[5];void dfs(int step){if (step == 5){jud(choose);return;}//選choose[step] = 1;dfs(step + 1);choose[step] = 0;//不選dfs(step + 1);}

判斷情況是否成立（1）

隨后我們進(jìn)行判斷函數(shù)jud的書(shū)寫，為了防止同一組數(shù)組不同的情況互相影響，我們創(chuàng)建一個(gè)臨時(shí)的數(shù)組 arr，復(fù)制arr的信息到其中，隨后對(duì) arr進(jìn)行操作。

之后創(chuàng)建i和j，分別用于遍歷行和列。

由于i和j的值不同，點(diǎn)燈還是滅燈的個(gè)數(shù)也不同（因?yàn)橛锌赡茉谶吔纾Ｒ虼?，我們?chuàng)建一個(gè)函數(shù)change，用于改變arr【i】【j】周圍能改變的燈的亮滅情況。

void jud(int* choose){int _arr[5][5];memcpy(_arr, arr, 25 * 4);//對(duì)第一行進(jìn)行操作int i = 0;//用于遍歷行int j = 0;//用于遍歷列for (j = 0; j < 5; j++){if (choose[j] == 1)//相當(dāng)于arr【0】【j】被選擇了{(lán)change(_arr, 0, j);//...}}}

實(shí)現(xiàn)亮滅改變函數(shù)

羅列情況，改變周圍燈的亮滅情況，如果你不想寫這么多的代碼，也可以把剛開(kāi)始創(chuàng)建的數(shù)組改為7x7大小，就可以不用考慮邊界了。

void change(int _arr[5][5], int i, int j){_arr[i][j] = !_arr[i][j];if (i == 0){_arr[i + 1][j] = !_arr[i + 1][j];if (j == 0){_arr[i][j+1] = !_arr[i][j+1];}else if (j == 4){_arr[i][j-1] = !_arr[i][j-1];}else{_arr[i][j - 1] = !_arr[i][j - 1];_arr[i][j + 1] = !_arr[i][j + 1];}}else if (i == 4){_arr[i - 1][j] = !_arr[i - 1][j];if (j == 0){_arr[i][j + 1] = !_arr[i][j + 1];}else if (j == 4){_arr[i][j - 1] = !_arr[i][j - 1];}else{_arr[i][j - 1] = !_arr[i][j - 1];_arr[i][j + 1] = !_arr[i][j + 1];}}else{_arr[i - 1][j] = !_arr[i - 1][j];_arr[i + 1][j] = !_arr[i + 1][j];if (j == 0){_arr[i][j+1] = !_arr[i][j+1];}else if (j == 4){_arr[i][j - 1] = !_arr[i][j - 1];}else{_arr[i][j - 1] = !_arr[i][j - 1];_arr[i][j + 1] = !_arr[i][j + 1];}}}

判斷情況是否成立（2）

因?yàn)閷?duì)第一行的每一次選擇也算走了一步，所以在每種情況下設(shè)置一個(gè)變量time，記錄當(dāng)前走了幾步，一旦time超過(guò)6，就立馬return。

注意：第一行只有五個(gè)數(shù)，因此在第一行的選擇中time不可能超過(guò)6，因此不需要在對(duì)第一行的選擇中進(jìn)行判斷。

void jud(int* choose){int _arr[5][5];memcpy(_arr, arr, 25 * 4);int time = 0;//對(duì)第一行進(jìn)行操作int i = 0;//用于遍歷行int j = 0;//用于遍歷列for (j = 0; j < 5; j++){if (choose[j] == 1)//相當(dāng)于arr【0】【j】被選擇了{(lán)time++;change(_arr, 0, j);}}//...//對(duì)2，3，4，5行進(jìn)行操作}

隨后對(duì)第2，3，4，5行進(jìn)行選擇，對(duì)第二行的選擇次數(shù)，是源于第一行選擇完之后還有幾個(gè)滅著的燈。

因此，我們對(duì)上一行進(jìn)行遍歷，如果_arr【i-1】【j】==0，就把time+1，同時(shí)點(diǎn)一下_arr【i】【j】。

注意：此時(shí)，time已經(jīng)有可能超過(guò)6了，因此需要進(jìn)行判斷。

void jud(int* choose){int _arr[5][5];memcpy(_arr, arr, 25 * 4);int time = 0;//對(duì)第一行進(jìn)行操作int i = 0;//用于遍歷行int j = 0;//用于遍歷列for (j = 0; j < 5; j++){if (choose[j] == 1)//相當(dāng)于arr【0】【j】被選擇了{(lán)time++;change(_arr, 0, j);}}//...//對(duì)2，3，4，5行進(jìn)行操作for (i = 1; i < 5; i++){for (j = 0; j < 5; j++){if (_arr[i - 1][j] == 0){time++;if (time > 6){return;}change(_arr, i, j);}}}//...}

現(xiàn)在，我們已經(jīng)對(duì)1 ~ 5行全部選擇完畢，但是不確定是否全部都為1，因此需要進(jìn)行遍歷一次，一旦出現(xiàn)為0的情況，說(shuō)明這種情況不可取，馬上返回。

//檢測(cè)數(shù)組中是否全部為1for (i = 0; i < 5; i++){for (j = 0; j < 5; j++){if (_arr[i][j] == 0){return;}}}//...//運(yùn)行到這里，說(shuō)明此種方案可行

對(duì)輸出數(shù)據(jù)的處理

題目要求我們輸出所有可行的方案中步數(shù)最少的一種所消耗的步數(shù)，如果沒(méi)有可行方案則返回-1。

因此，我們?cè)O(shè)置一個(gè)全局變量min_time并令其初始化為一個(gè)大于6的數(shù)，一旦出現(xiàn)一個(gè)time小于min_time，就把min_time更新為time。

如果還有更小的time，就能再次更新。

int arr[5][5];int choose[5];int min_time = 10;

//運(yùn)行到這里，說(shuō)明此種方案可行min_time = time;return;//...

隨后，我們進(jìn)行最后的處理。

當(dāng)dfs（0）結(jié)束之后，我們得到了一個(gè)min_time，因?yàn)樗某跏贾荡笥?，所以只要有可行方案存在，該值就一定會(huì)被改變，否則，它就依然還是原來(lái)的值。

所以，我們?cè)O(shè)置一個(gè)if語(yǔ)句，如果該值為10（初始值），代表沒(méi)有可行方案，打印-1后換行。

如果該值不等于10，就打印這個(gè)數(shù)后換行，代表最小步數(shù)為該值。

注意：因?yàn)閙in_time是我們?cè)谌侄x的，因此打印完了以后不要忘記再將其重新賦值為10哦。（博主改了很久才想到這一點(diǎn)，TAT）

int main(){int n = 0;scanf("%d", &n);while (n--){int i = 0;for (i = 0; i < 5; i++){int j = 0;for (j = 0; j < 5; j++){scanf("%1d", &arr[i][j]);}}dfs(0);if (min_time == 10){printf("-1\n");}else{printf("%d\n", min_time);min_time = 10;}}return 0;}

感謝您的閱讀與耐心~ 如有錯(cuò)誤煩請(qǐng)指出~

關(guān)鍵詞： 編程算法