本文主要是介绍Acwing95 --- 费解的开关，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
我认为这道题非常不错，题出的very good，个人观点hhh。
考点：DFS + 二进制枚举 + 题意转换
你玩过“拉灯”游戏吗？
25 盏灯排成一个 5×5 的方形。
每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。
下面这种状态
10111 01101 10111 10000 11011在改变了最左上角的灯的状态后将变成：
01111 11101 10111 10000 11011再改变它正中间的灯后状态将变成：
01111 11001 11001 10100 11011给定一些游戏的初始状态，编写程序判断游戏者是否可能在 66 步以内使所有的灯都变亮。
输入格式
第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 66 步以内无法使所有灯变亮，则输出 −1。
数据范围
0<n≤500
输入样例：
3 00111 01011 10001 11010 1110011101 11101 11110 11111 1111101111 11111 11111 11111 11111输出样例：
3 2 -1
拿到这道题也是很头疼，无从下手。
首先分析这道题，题中明确描述，每个按钮只可以点击一次，因为咱们一般都是通过有规律的操作完成某一特定结果，所以这里咱们定一个点击方向，有上到下逐层点击，为了保证当前点的改变，我们可以点击其下面的点以此来达到改变当前点的目的，这里就可以利用递归层次枚举四个方向的点，这个很经典的用法。
为什么要改变下方点来达到改变当前点呢？因为如果改变当前点，那么咱们是逐层点亮，若点亮当前点，那么当前点的上面的点也会被点亮。
char g[10][10];
int dx[5] = {0,-1,0,1,0};
int dy[5] = {0,0,1,0,-1};
void turn(int x , int y)
{for(int i = 0;i <= 4;i++){int a = x + dx[i];int b = y + dy[i];if(a >= 0 && a < 5 && b >= 0 && b < 5)//不越界{g[a][b] ^= 1;//0转1,1转0}}
}上面的代码是点亮的操作，通过调用 turn 函数进行。
而为了让其从上到下的操作，我们应该如何处理第一层呢？首先一共五个开关，每个开关对应了两种情况（0或1），那么也就是32种情况（1 << 5），那么我们就利用二进制枚举这32种情况，这里等后面解释32种情况地具体含义。
然后第一行就可以认定其固定不动，之后逐层考虑并操作直到第五层，判断，如果当前第五层全亮那么当前枚举的方案成立，不断比较大小并返回其最小操作次数。
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 1000000;
char g[10][10];
int dx[5] = {0,-1,0,1,0};
int dy[5] = {0,0,1,0,-1};
void turn(int x , int y)//点亮操作
{for(int i = 0;i <= 4;i++){int a = x + dx[i];int b = y + dy[i];if(a >= 0 && a < 5 && b >= 0 && b < 5){g[a][b] ^= 1;}}
}int work()
{int ans = INF;for(int k = 0;k < (1 << 5);k++){int res = 0;char backup[10][10];memcpy(backup , g , sizeof g);//记录棋盘，便于刷新for(int j = 0;j < 5;j++){//（k=8）01000 >> 0 = 0,01000 >> 1 = 0,01000 >> 2 = 0,01000 >> 3 = 1,01000 >> 4 = 0;if(k >> j & 1)//利用二进制指数型枚举32次第一层所有可能得操作，让k（十转二的k）右移其对应的j位判断其与1的关系达到32次不同可能性//这里的操作不是让其全调为1，而是枚举的32种情况对应的操作方式{res++;turn(0,j);}}//遍历2-5层for(int i = 0;i < 4;i++){for(int j = 0;j < 5;j++){if(g[i][j] == '0'){res++;turn(i + 1 , j);}}}//判断是否successbool is_successful = true;for(int j = 0;j < 5;j++){if(g[4][j] == '0') is_successful = false;break;}if(is_successful) ans = min(ans , res);memcpy(g , backup , sizeof g);//重置棋盘}if(ans > 6) ans = -1;return ans;
}
int main()
{int T;cin >> T;while(T--){for(int i = 0;i < 5;i++){cin >> g[i];}cout << work() << endl;}return 0;
}这里投个稿，希望有哪位大佬回答一下这份代码为何处理不了500...这组答案，请指教！！！
在Acwing并没有得到AC...
上面的题解是没毛病的，但是代码有些许的数据处理不了（服了）。
这篇关于Acwing95 --- 费解的开关的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
