一步一步地完成題目——費解的開關（C/C++語言）遞推、遞歸、順序思維-每日快報

前言

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

題目

參考題目：費解的開關

詳細的題目信息相信大家都已經知道了，因此這里為了簡潔只展示輸入輸出格式及數據范圍。

【資料圖】

核心思維

本題利用遞推做的核心思想很簡單，即當這個5x5數組的第一行被處理完過后，想要開啟第一行仍然滅著的燈，則必須點擊該燈的下一行的相同位置。

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

如圖所示：

假設我們第一行只點一次，即被藍色X的地方，點完后會變成這樣：

如果我們想讓第一行的第一個、第四個變亮，那么第二行的第一個、第四個就是必點的。

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

寫出數據輸入格式

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

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上數據輸入時，每個數據之間沒有空格，因此要控制scanf每次讀取數據的寬度。代碼中的“//...”代表接下來從此處開始寫。

枚舉第一行的選擇

這里我們使用遞歸的方法，即在1 ~ 5里面選出1 ~ 5個數，每一種選法都是一種第一行的選擇。創建遞歸函數dfs（int step），step代表當前枚舉的位置，在外面創建數組choose代表遞歸時每個位置的狀態，每次枚舉當前位置選或者不選，五個位置都枚舉結束后就代表形成了一種情況，隨后利用判斷函數jud對這種情況進行判斷。

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）

隨后我們進行判斷函數jud的書寫，為了防止同一組數組不同的情況互相影響，我們創建一個臨時的數組 arr，復制arr的信息到其中，隨后對 arr進行操作。

之后創建i和j，分別用于遍歷行和列。

由于i和j的值不同，點燈還是滅燈的個數也不同（因為有可能在邊界）。因此，我們創建一個函數change，用于改變arr【i】【j】周圍能改變的燈的亮滅情況。

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

實現亮滅改變函數

羅列情況，改變周圍燈的亮滅情況，如果你不想寫這么多的代碼，也可以把剛開始創建的數組改為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）

因為對第一行的每一次選擇也算走了一步，所以在每種情況下設置一個變量time，記錄當前走了幾步，一旦time超過6，就立馬return。

注意：第一行只有五個數，因此在第一行的選擇中time不可能超過6，因此不需要在對第一行的選擇中進行判斷。

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

隨后對第2，3，4，5行進行選擇，對第二行的選擇次數，是源于第一行選擇完之后還有幾個滅著的燈。

因此，我們對上一行進行遍歷，如果_arr【i-1】【j】==0，就把time+1，同時點一下_arr【i】【j】。

注意：此時，time已經有可能超過6了，因此需要進行判斷。

void jud(int* choose){int _arr[5][5];memcpy(_arr, arr, 25 * 4);int time = 0;//對第一行進行操作int i = 0;//用于遍歷行int j = 0;//用于遍歷列for (j = 0; j < 5; j++){if (choose[j] == 1)//相當于arr【0】【j】被選擇了{time++;change(_arr, 0, j);}}//...//對2，3，4，5行進行操作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);}}}//...}

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

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

對輸出數據的處理

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

因此，我們設置一個全局變量min_time并令其初始化為一個大于6的數，一旦出現一個time小于min_time，就把min_time更新為time。

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

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

//運行到這里，說明此種方案可行min_time = time;return;//...

隨后，我們進行最后的處理。

當dfs（0）結束之后，我們得到了一個min_time，因為它的初始值大于6，所以只要有可行方案存在，該值就一定會被改變，否則，它就依然還是原來的值。

所以，我們設置一個if語句，如果該值為10（初始值），代表沒有可行方案，打印-1后換行。

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

注意：因為min_time是我們在全局定義的，因此打印完了以后不要忘記再將其重新賦值為10哦。（博主改了很久才想到這一點，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;}

感謝您的閱讀與耐心~ 如有錯誤煩請指出~

關鍵詞： 編程算法