kuai

用户名：kuai

访问量：5100

签　名：

等　　级
排　　名	4788
经　　验	1637
参赛次数	0
文章发表	10
年　　龄	0
在职情况	学生
学　　校	黄龙山职院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-开灯游戏-题解-DFS模板题(C++代码)
浏览：479

蓝桥杯算法提高VIP-彩票-find()函数
浏览：275

蓝桥杯算法提高VIP-我们的征途是星辰大海-模拟+读题
浏览：265

你可能喜欢

蓝桥杯算法提高VIP-开灯游戏-题解-DFS模板题(C++代码)

　　作者: kuai　　　　发表时间：2020-04-18 12:22:05 浏览：479　|　评论：0　

原题链接：蓝桥杯算法提高VIP-开灯游戏

```cpp
/*
题目描述
有9盏灯与9个开关，编号都是1~9。

每个开关能控制若干盏灯，按下一次会改变其控制的灯的状态(亮的变成不亮，不亮变成亮的)。

具体如下：

第一个开关控制第二，第四盏灯；

第二个开关控制第一，第三，第五盏灯；

第三个开关控制第二，第六盏灯；

第四个开关控制第一，第五，第七盏灯；

第五个开关控制第二，第四，第六，第八盏灯；

第六个开关控制第三，第五，第九盏灯；

第七个开关控制第四，第八盏灯；

第八个开关控制第五，第七，第九盏灯；

第九个开关控制第六，第八盏灯。

开始时所有灯都是熄灭的，开关是关闭着的。要求按下若干开关后，使得只有4盏灯亮着。
输入
无
输出
输出所有可能的方案，每行一个方案，每一行有9个字符，从左往右第i个字符表示第i个开关的状态(" 0" 表示关闭，" 1" 表示打开)，按字典序输出。下面的样例输出只是部分方案。 
样例输入
无
样例输出
000001011 
000001110 
000001111 
*/

/*
重点：
	
思路： 
	dfs 按位深搜 
*/
#include<iostream>
using namespace std;

int a[10];			// 记录每个按钮的状态 
int light[10];		// 记录灯的开关 状态

void f(int i){
	//修改第 i 栈灯的状态
	if(light[i] == 0)	light[i] = 1;
	else light[i] = 0; 
}

bool check(){
	int cnt = 0;
	for(int i = 1;i <= 9;++i )
		if(light[i])
			++cnt;
	if(cnt == 4)	return true;
	else return false;	
}
void dfs(int s){
	// 当前走到第 s 栈灯
	
	//判断终点 
	if(s == 10){
		if(check()){
			for(int i = 1;i <= 9;++i)
			cout<<a[i];
		cout<<endl;
		}
		return ;
	} 
	
	// 对所有可走点 dfs 
	if(s == 1){
		// 0  状态，什么也不做 
		a[s] = 0;
		dfs(s+1);
		// 1
		a[s] = 1;
		f(2);
		f(4);
		dfs(s+1);
		// 状态恢复 
		f(2);
		f(4);
	}
	else if(s == 2){
		// 0  
		a[s] = 0;
		dfs(s+1);
		// 1
		a[s] = 1;
		f(1);
		f(3);
		f(5);
		dfs(s+1);
		
	// 状态恢复 
		f(1);
		f(3);
		f(5);
	}
	else if(s == 3){
		// 0  
		a[s] = 0;
		dfs(s+1);
		// 1
		a[s] = 1;
		f(2);
		f(6);
		dfs(s+1);
		
	// 状态恢复 
		f(2);
		f(6);
	}
	else if(s == 4){
		// 0  
		a[s] = 0;
		dfs(s+1);
		// 1
		a[s] = 1;
		f(1);
		f(5);
		f(7);
		dfs(s+1);
		
	// 状态恢复 
		f(1);
		f(5);
		f(7);
	}
	else if(s == 5){
		// 0  
		a[s] = 0;
		dfs(s+1);
		// 1
		a[s] = 1;
		f(2);
		f(4);
		f(6);
		f(8);
		dfs(s+1);
		
	// 状态恢复 
		f(2);
		f(4);
		f(6);
		f(8);
	}
	else if(s == 6){
		// 0  
		a[s] = 0;
		dfs(s+1);
		// 1
		a[s] = 1;
		f(3);
		f(5);
		f(9);
		dfs(s+1);
		
	// 状态恢复 
		f(3);
		f(5);
		f(9);
	}
	else if(s == 7){
		// 0  
		a[s] = 0;
		dfs(s+1);
		// 1
		a[s] = 1;
		f(4);
		f(8);
		dfs(s+1);
		
	// 状态恢复 
		f(4);
		f(8);
	}
	else if(s == 8){
		// 0  
		a[s] = 0;
		dfs(s+1);
		// 1
		a[s] = 1;
		f(5);
		f(7);
		f(9);
		dfs(s+1);
		
	// 状态恢复 
		f(5);
		f(7);
		f(9);
	}	
	else if(s == 9){
		// 0  
		a[s] = 0;
		dfs(s+1);
		// 1
		a[s] = 1;
		f(6);
		f(8);
		dfs(s+1);
		
	// 状态恢复 
		f(6);
		f(8);
	}	
}

int main(){
	dfs(1);
	
	return 0;
}
```

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

kuai

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

字符串输入输出函数（Java代码）

输出九九乘法表（C语言代码）

第一

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蓝桥杯算法提高VIP-开灯游戏-题解-DFS模板题(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单的a+b （C语言代码）

字符逆序（C语言代码）

震宇大神的杀毒软件（C语言代码）

Quadratic Equation （C语言代码）

输入输出格式练习（C语言代码）

陶陶摘苹果2 （C语言代码）

kuai

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

字符串输入输出函数 （Java代码）

输出九九乘法表 （C语言代码）

第一

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蓝桥杯算法提高VIP-开灯游戏-题解-DFS模板题(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单的a+b （C语言代码）

字符逆序 （C语言代码）

震宇大神的杀毒软件 （C语言代码）

Quadratic Equation （C语言代码）

输入输出格式练习 （C语言代码）

陶陶摘苹果2 （C语言代码）

字符串输入输出函数（Java代码）

输出九九乘法表（C语言代码）

　　评论区

字符逆序（C语言代码）

震宇大神的杀毒软件（C语言代码）

输入输出格式练习（C语言代码）