題目背景
上元佳節(jié)，廟會(huì)里舉辦著各式各樣的慶典活動(dòng)，牛寶也興奮地參與其中。突然，他被一個(gè)新穎的點(diǎn)燈游戲所吸引，游戲要求最終點(diǎn)亮所有在場(chǎng)的花燈，每盞燈都有開關(guān)兩種狀態(tài)，每一次點(diǎn)擊在場(chǎng)的一盞任意狀態(tài)的花燈，其自身和四周的的花燈都會(huì)改變其開關(guān)狀態(tài)。

例如

3*3的花燈陣

0 1 1

1 0 0

1 0 1

點(diǎn)一下最中間的燈【2,2】就變成了

0 0 1

0 1 1

1 1 1

再點(diǎn)一下左上角的燈【1,1】就變成了

1 1 1

1 1 1

1 1 1

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

題目描述
給出3*3的花燈陣各盞花燈的初始開關(guān)狀態(tài)，請(qǐng)你按照序號(hào)從小到大的順序點(diǎn)亮花燈（從左上角到右下角序號(hào)依次為1-9），同時(shí)要求點(diǎn)亮的次數(shù)最少（避免多余的點(diǎn)亮步驟），使得最終全部花燈均被點(diǎn)亮。

輸入格式
九個(gè)數(shù)字，3*3的格式輸入，每?jī)蓚€(gè)數(shù)字中間只有一個(gè)空格，表示燈初始的開關(guān)狀態(tài)。（0表示關(guān)，1表示開）

輸出格式
按照序號(hào)從小到大的順序點(diǎn)亮花燈（從左上角到右下角序號(hào)依次為1-9），輸出點(diǎn)亮的序號(hào)集合（每?jī)蓚€(gè)序號(hào)之間用空格隔開）。

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

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

代碼如下:

#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) { //開關(guān)燈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 ;//剪枝，不剪枝會(huì)超時(shí)//超過(guò)最小的次數(shù)就返回，初始次數(shù)為10，規(guī)律:它總共步驟不會(huì)超過(guò)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;//將二維數(shù)組轉(zhuǎn)換為一維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; }

當(dāng)然，因?yàn)榘?下等于沒(méi)有按，所以我們可以增加一個(gè)標(biāo)記數(shù)組，這樣就會(huì)少按很多重復(fù)的無(wú)效的次數(shù)，相當(dāng)于剪枝。

代碼如下:

#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) { //開關(guān)燈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 ;//剪枝，不剪枝會(huì)超時(shí)//超過(guò)最小的次數(shù)就返回，初始次數(shù)為10，規(guī)律:它總共步驟不會(huì)超過(guò)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;//將二維數(shù)組轉(zhuǎn)換為一維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; }

當(dāng)然，如果你想不到怎么把二維數(shù)組轉(zhuǎn)換為一維，也可以這樣寫：

#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; }

總結(jié)

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

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