95. 费解的开关（位运算枚举)

本文主要是介绍95. 费解的开关（位运算枚举)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

费解的开关
题目
提交记录
讨论
题解
视频讲解

你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。

输入格式
第一行输入正整数n，代表数据中共有n个待解决的游戏初始状态。

以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。

输出格式
一共输出n行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。

数据范围
0<n≤500
输入样例：
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
输出样例：

3
2
-1
难度：中等
时/空限制： 1s / 256MB
总通过数： 715
总尝试数： 1201
来源：《算法竞赛进阶指南》

https://www.acwing.com/problem/content/description/97/

**思路：**http://poj.org/problem?id=3279 poj这道题的简化版，只需要确定第一行的状态，其他行的状态就确定了，然后枚举取最小即可。

#include <cstdio>
#include <cmath>
#include <vector>
#include <iostream>
#include <cstring>
#include <map>using namespace std;#define INF 0x3f3f3f3f
int a[10][10],tmp[10][10];
int dirx[] = {1,-1,0,0,0};
int diry[] = {0,0,-1,1,0};void swap(int x,int y)
{for(int i = 0;i < 5;i++){int dx = x + dirx[i];int dy = y + diry[i];if(dx >= 0 && dy >= 0 && dx < 5 && dy < 5){tmp[dx][dy] ^= 1;}}
}int solve(int sta)
{for(int i = 0;i < 5;i++){for(int j = 0;j < 5;j++){tmp[i][j] = a[i][j];}}int ans = 0;for(int i = 0;i < 5;i++){if(1 & (sta >> (i))){ans++;swap(0,i);}}for(int i = 1;i < 5;i++){for(int j = 0;j < 5;j++){if(tmp[i - 1][j] == 0){swap(i,j);ans++;}}}for(int i = 0;i < 5;i++){for(int j = 0;j < 5;j ++){if(tmp[i][j] != 1){ans = INF;}}}return ans;
}int main()
{int T;scanf("%d",&T);while(T--){int ans = INF;for(int i = 0;i < 5;i++){for(int j = 0;j < 5;j++){scanf("%1d",&a[i][j]);}}for(int i = 0;i < (1 << 5);i++){ans = min(solve(i),ans);}if(ans > 6)cout << -1 << endl;else cout << ans << endl;}return 0;
}