AcWing-95.费解的开关

¶首先来首歌曲来放松一下吧！

题目链接：95.费解的开关

¶题目背景：

¶题目描述

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

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

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

再改变它正中间的灯后状态将变成：

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

¶输入格式

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

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

¶输出格式

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

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

¶数据范围

0<n≤500

¶输入样例：

¶输出样例：

1
2
3

3
2
-1

¶题目分析：

¶题目要求：

给定一个 5 x 5 的矩阵，想要全部变成1，求最少的步数，并且改变一个上下左右都换变化！

¶解题思路：

我们可以一层一层去想，先看第一层，如果第一层有 0，我们需要在下一层的正下方的那个点作为中心改变状态即可，使上面的0变为1,；同样，第一层结束，要想使第二层也全变为1，做法一样，使有0 的正下方作为中心改变即可；最终只需要判断改变了前四行后，第五行有没有全部变为1即可，若没有变为1，则此种情况并不合法。

第一层的变化自然是有2的五次方，仍然想成二进制来表示，只需枚举这些所有情况即可，将可达到最终状态的最小值找出来即可！

也就是说，如果只考虑第一层，他的开关方法有2的五次方，最终可以使最后一层全部变为1的就是一组解！

注意：本题输入是没有空格的，我以为有空格，用int来存储的，结果出了问题，可以使用char数组来存储即可！

为了方便的复制一份g数组，使用的cstring头文件的memcpy函数！

memcpy()函数：

第一个参数：备份数组
第二个参数：原数组
第三个参数：用sizeof计算的大小

在进行0,1取反时，直接和1异或即可！

char类型的 0 和 1 也可以：对应的ASCII码分别为48和49，二进制如下：

110000 110001

异或后结果没有问题！

yxc大神的视频讲解：点击这里！

¶题解：

#include <cstring>
#include <iostream>

using namespace std;

int n;
char g[10][10];
char backup[10][10];

int dx[5] = {0, -1, 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};

bool in(int x, int y)
{
	return x >= 0 && x < 5 && y >= 0 && y <= 5;
}

// 改变五个值
void turn(int x, int y)
{
	for(int i = 0; i < 5; i++)
	{
		int a = x + dx[i], b = y + dy[i];
		if(in(a, b)) g[a][b] ^= 1;
	}
}

int solve()
{
	int ans = 0x3f;
	//二进制的1来表示按那个灯
	for(int i = 0; i < 1 << 5; i++)
	{
		int res = 0;
        // 扫描第一层按过的开关，并进行修改
		for(int  j = 0; j < 5; j++)
		{
			if(i >> j & 1)
			{
				res ++;
				turn(0, j);
			}
		}
		
        // 扫描前四层
		for(int j = 0; j < 4; j++)
		{
			for(int k = 0; k < 5; k++)
			{
				if(g[j][k] == '0')
				{
					res ++;
					turn(j + 1, k);
				}
			}
		}
		
        // 扫描最后一层
		bool flag = true;
		for(int j = 0; j < 5; j++)
			if(g[4][j] == '0') 
			{
				flag = false;
				break;
			}
		
        // 还原g数组的状态
		memcpy(g, backup, sizeof g);
				
		if(flag) ans = min(ans, res);
	}
	if(ans > 6) return -1;
	return ans;
}

int main()
{
	cin >> n;
	
    while(n --)
	{	
		for(int i = 0; i < 5; i++) cin >> g[i];
		
		memcpy(backup, g, sizeof g);
					
		cout << solve() << endl;
	}
	return 0;
}