題目描述
有9盞燈與9個(gè)開關(guān)，編號(hào)都是1~9。

每個(gè)開關(guān)能控制若干盞燈，按下一次會(huì)改變其控制的燈的狀態(tài)(亮的變成不亮，不亮變成亮的)。

具體如下：

第一個(gè)開關(guān)控制第二，第四盞燈；

第二個(gè)開關(guān)控制第一，第三，第五盞燈；

第三個(gè)開關(guān)控制第二，第六盞燈；

第四個(gè)開關(guān)控制第一，第五，第七盞燈；

第五個(gè)開關(guān)控制第二，第四，第六，第八盞燈；

第六個(gè)開關(guān)控制第三，第五，第九盞燈；

第七個(gè)開關(guān)控制第四，第八盞燈；

第八個(gè)開關(guān)控制第五，第七，第九盞燈；

第九個(gè)開關(guān)控制第六，第八盞燈。

開始時(shí)所有燈都是熄滅的，開關(guān)是關(guān)閉著的。要求按下若干開關(guān)后，使得只有4盞燈亮著。
輸入
無
輸出
輸出所有可能的方案，每行一個(gè)方案，每一行有9個(gè)字符，從左往右第i個(gè)字符表示第i個(gè)開關(guān)的狀態(tài)(" 0" 表示關(guān)閉，" 1" 表示打開)，按字典序輸出。下面的樣例輸出只是部分方案。
樣例輸入
無
樣例輸出
000001011
000001110
000001111
思路：數(shù)據(jù)量不大，直接暴力搜索，然后判斷是否符合題意。注意字典序是從小到大。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=15; int vis[maxx]; int a[maxx];inline int check() {memset(a,0,sizeof(a));if(vis[1]) a[2]++,a[4]++;if(vis[2]) a[1]++,a[3]++,a[5]++;if(vis[3]) a[2]++,a[6]++;if(vis[4]) a[1]++,a[5]++,a[7]++;if(vis[5]) a[2]++,a[4]++,a[6]++,a[8]++;if(vis[6]) a[3]++,a[5]++,a[9]++;if(vis[7]) a[4]++,a[8]++;if(vis[8]) a[5]++,a[7]++,a[9]++;if(vis[9]) a[6]++,a[8]++;int num=0;for(int i=1;i<=9;i++) if(a[i]&1) num++;return num==4; } inline void dfs(int x) {if(x==10){if(check()){for(int i=1;i<=9;i++) cout<<vis[i];cout<<endl;}return ;}dfs(x+1);//先考慮不開的情況，這樣字典序就是最小的了。if(vis[x]==0) {vis[x]=1;dfs(x+1);vis[x]=0;} } int main() {memset(vis,0,sizeof(vis));dfs(1);return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][算法提高VIP]开灯游戏（dfs）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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