题目描述
你玩过“拉灯”游戏吗?
$25$ 盏灯排成一个 $5×5 $ 的方形。
每一个灯都有一个开关,游戏者可以改变它的状态。
每一步,游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 $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
思路:
每改变一个灯,其上下左右的灯的亮灭都会改变。将灯的亮灭按一行一行来看,每一行灯的操作,由上一行灯的亮灭状态决定。上一行的 $i$ 位置灯是灭的,那么就需调整下一行的 $i$ 位置的开关,使上一行的 $i$ 位置灯亮起。
由于灯的操作只有两种情况,按或者不按。因此灯是否操作可以用二进制来表示。枚举每一行的操作,可以将由0,1组成的数字串转化成10进制的数,00000就是全部不操作。这样每个数字串都对应一个10进制的数。在需要调查第i位数字是1还是0的时候只需要让十进制的数右移>>i位(此时第i位就在个位)再&1将个位数字取出即可。
灯是否能全亮可以根据最后一行能不能全被点亮来判断,如果最后一行不能全亮说明整个没办法全亮。
在操作过程中每一个状态会枚举很多次,每次枚举都要从初始状态枚举,所以需要用一个数组备份
先枚举第一行的所有按法,再根据第一行的按法去按后面的行。第一行枚举的并不是灯亮不亮,而是对该行所有灯按不按的所有情况的枚举,第一行的按法一旦确定(第一行的灯亮不亮也就确定了),后面的状态就全部确定了。再从所有第一行按法中选出步数最小的那一种按法。
为什么要枚举第一行的所有操作呢,因为第一行在操作后确定了状态,后面的行的操作也就确定了。因此是否能够全点亮和点亮需要多少步数都是由第一行的状态决定的。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 6;
char graph[N][N], backup[N][N]; // 在原棋盘操作前先备份一下
int dx[5] = { -1, 0, 1, 0, 0 };
int dy[5] = { 0, 1, 0, -1, 0 };
void turn(int x, int y) // 在graph里改变操作点的其他方向的灯的亮度
{
for (int i = 0; i < 5; i++)
{
int a = x + dx[i];
int b = y + dy[i];
if (a < 0 || a >= 5 || b < 0 || b >= 5) // 超出边界
continue;
graph[a][b] = (graph[a][b] < '1') ? '1' : '0'; // 改变状态
}
}
int main()
{
int T;
cin >> T;
while (T--)
{
for (int i = 0; i < 5; i++) // 输入灯的状态
cin >> graph[i];
int maxN = 10; // 最大步数
for (int op = 0; op < 32; op++) // // 第一行的按法(在这里 1 表示按了, 0 表示不按),这里只是为了输出第一行按完之后的状态
{
memcpy(backup, graph, sizeof graph);
int step = 0;
for (int i = 0; i < 5; i++)
if (op >> i & 1) // 如果第一行的第i位是1,就按第i位
{
step++;
turn(0, i);
}
// 通过第一行按完的状态,按第2,3,4行
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (graph[i][j] == '0')
{
step++;
turn(i + 1, j);
}
// 判断最后一行是否全亮,如果不是全亮说明没办法使其全亮
bool dark = false;
for (int i = 0; i < 5; i++)
if (graph[4][i] == '0')
{
dark = true;
break;
}
// 对于32种情况的这一种,如果所有的全亮就记录下步数
if (!dark)
maxN = min(maxN, step);
memcpy(graph, backup, sizeof graph); // 恢复现场
}
if (maxN > 6)
maxN = -1;
cout << maxN << endl;
}
return 0;
}