題目背景
上元佳節，廟會里舉辦著各式各樣的慶典活動，牛寶也興奮地參與其中。突然，他被一個新穎的點燈游戲所吸引，游戲要求最終點亮所有在場的花燈，每盞燈都有開關兩種狀態，每一次點擊在場的一盞任意狀態的花燈，其自身和四周的的花燈都會改變其開關狀態。

例如

3*3的花燈陣

0 1 1

1 0 0

1 0 1

點一下最中間的燈【2,2】就變成了

0 0 1

0 1 1

1 1 1

再點一下左上角的燈【1,1】就變成了

1 1 1

1 1 1

1 1 1

最終輸出點亮花燈的序號（從左上角到右下角序號依次為1-9），答案即點亮1號燈和5號燈。 為了獎品，牛寶只能嘗試破解3*3的花燈陣，你能協助他嗎？

題目描述
給出3*3的花燈陣各盞花燈的初始開關狀態，請你按照序號從小到大的順序點亮花燈（從左上角到右下角序號依次為1-9），同時要求點亮的次數最少（避免多余的點亮步驟），使得最終全部花燈均被點亮。

輸入格式
九個數字，3*3的格式輸入，每兩個數字中間只有一個空格，表示燈初始的開關狀態。（0表示關，1表示開）

輸出格式
按照序號從小到大的順序點亮花燈（從左上角到右下角序號依次為1-9），輸出點亮的序號集合（每兩個序號之間用空格隔開）。

輸入輸出樣例
輸入
0 1 1
1 0 0
1 0 1
輸出
1 5
說明/提示
牛寶正在腦海中不停地進行嘗試。。。

解題思路:
從左上到右下1-9的順序進行點亮深搜，一旦點亮該燈，自身和其四周燈亮滅情況變化，保留點亮過程燈號；
深搜這條路徑無法點亮所有的燈則進行回溯，自身和其四周燈亮滅情況變化。
深搜邊界條件即點亮所有的燈，一旦有更少步數的進行更新方案。

代碼如下:

#include <iostream> using namespace std; const int N = 5; int g[N][N]; int ans = 10; int path[10]; bool vis[10]; int paths[10];void turn(int x, int y) { //開關燈g[x][y] = 1 - g[x][y];g[x - 1][y] = 1 - g[x - 1][y];g[x + 1][y] = 1 - g[x + 1][y];g[x][y + 1] = 1 - g[x][y + 1];g[x][y - 1] = 1 - g[x][y - 1]; }void dfs(int n) {if (n > ans)return ;//剪枝，不剪枝會超時//超過最小的次數就返回，初始次數為10，規律:它總共步驟不會超過9次int sum = 0;for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)sum += g[i][j];if (sum == 9) {ans = min(ans, n - 1);for (int i = 1; i <= ans; i++) {paths[i] = path[i];}return ;}for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++) {turn(i, j);path[n] = (i - 1) * 3 + j;//將二維數組轉換為一維dfs(n + 1);turn(i, j);}}int main() {for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)cin >> g[i][j];dfs(1);for (int i = 1; i <= ans; i++) {cout << paths[i] << " ";}return 0; }

當然，因為按2下等于沒有按，所以我們可以增加一個標記數組，這樣就會少按很多重復的無效的次數，相當于剪枝。

代碼如下:

#include <iostream> using namespace std; const int N = 5; int g[N][N]; int ans = 10; int path[10]; int paths[10]; bool vis[N][N];void turn(int x, int y) { //開關燈g[x][y] = 1 - g[x][y];g[x - 1][y] = 1 - g[x - 1][y];g[x + 1][y] = 1 - g[x + 1][y];g[x][y + 1] = 1 - g[x][y + 1];g[x][y - 1] = 1 - g[x][y - 1]; }void dfs(int n) {if (n > ans)return ;//剪枝，不剪枝會超時//超過最小的次數就返回，初始次數為10，規律:它總共步驟不會超過9次int sum = 0;for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)sum += g[i][j];if (sum == 9) {ans = min(ans, n - 1);for (int i = 1; i <= ans; i++) {paths[i] = path[i];}return ;}for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++) {if (!vis[i][j]) {vis[i][j] = true;turn(i, j);path[n] = (i - 1) * 3 + j;//將二維數組轉換為一維dfs(n + 1);vis[i][j] = false;turn(i, j);}}}int main() {for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)cin >> g[i][j];dfs(1);for (int i = 1; i <= ans; i++) {cout << paths[i] << " ";}return 0; }

當然，如果你想不到怎么把二維數組轉換為一維，也可以這樣寫：

#include<bits/stdc++.h> using namespace std; int s[5][5];int book[5][5];int small=10; int t[10]; int tt[10]; int change(int x,int y) {s[x][y]=1-s[x][y];s[x-1][y]=1-s[x-1][y];s[x+1][y]=1-s[x+1][y];s[x][y-1]=1-s[x][y-1];s[x][y+1]=1-s[x][y+1];return 0; } int dfs(int k) {if(k>small)return 0;int sum=0;for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){sum+=s[i][j];}}if(sum==9){if(k<small){small=k;for(int i=1;i<=k;i++){tt[i]=t[i];}}return 0;}for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){if(book[i][j]==0){if(i==1&&j==1)t[k+1]=1;if(i==1&&j==2)t[k+1]=2;if(i==1&&j==3)t[k+1]=3;if(i==2&&j==1)t[k+1]=4;if(i==2&&j==2)t[k+1]=5;if(i==2&&j==3)t[k+1]=6;if(i==3&&j==1)t[k+1]=7;if(i==3&&j==2)t[k+1]=8;if(i==3&&j==3)t[k+1]=9;change(i,j);book[i][j]=1;dfs(k+1);change(i,j);book[i][j]=0;} }}return 0; } int main() {for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){cin>>s[i][j];}}dfs(0);for(int i=1;i<=small;i++){cout<<tt[i]<<" ";}return 0; }

總結

以上是生活随笔為你收集整理的上元节的灯会(亮)-dfs的全部內容，希望文章能夠幫你解決所遇到的問題。

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