//2020.4.27
题目：费解的开关
题目描述：
链接：https://ac.nowcoder.com/acm/contest/998/D
来源：牛客网
你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
求解之路；
如果能6步全亮，那么从第一排开始，对其进行枚举，然后一次次得改变，看最后一行能否全亮
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int INF = 1e6;
int T;
char a[5][5],dx[5]={0,0,-1,0,1},dy[5]={0,1,0,-1,0};
//a数组用来存每次的情况，dx,dy是为了方便每一次改变对其上下左右得灯的状态
void turn(int x,int y){//改变灯的状态
int xi,yi;
for(int i = 0;i < 5;i ++)
{
xi = x+dx[i];yi = y+dy[i];
if(xi >= 0 && xi < 5 && yi >= 0 && yi < 5)
a[xi][yi] ^= 1;//通过异或运算 ，将其置为相反
}
}
int work()
{
int ans = INF;
for(int k = 0; k < 1 << 5; k++)//枚举第一行的所有情况
{
int cnt = 0;//操作次数
char temp[5][5];//保存数组
memcpy(temp, a, sizeof a);
for(int i = 0; i < 5; i++)//将当前a数组的情况转化为k枚举到的情况
if(k >> i & 1)
{
cnt++;
turn(0, i);
}
for(int i = 0; i < 4; i++)//前4行5列
for(int j = 0; j < 5; j++)
if(a[i][j] == '0')//如果是灭的
{
cnt++;
turn(i + 1, j);//操作它下方的当，使它变亮
}
bool is_ok = true;
for(int i = 0; i < 5; i++)//检查最后一行是否全亮
{
if(a[4][i] == '0')
{
is_ok = false;
break;
}
}
if(is_ok)
ans = min(ans, cnt);
memcpy(a, temp, sizeof a);//恢复现场，将a数组回复
}
if(ans > 6)
ans = -1;
return ans;
}
int main(){
cin >> T;
while(T--){
for(int i = 0;i < 5;i++)
for(int j = 0;j < 5;j++){
cin >> a[i][j];
}
cout << work() << endl;;
}
return 0;
}
京公网安备 11010502036488号