费解的开关

题目描述

你玩过“拉灯”游戏吗?

\(25\) 盏灯排成一个 \(5 \times 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

算法

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include "iostream"
#include "cstring"

using namespace std;

const int N = 6;

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

void turn(int x, int y) {
//改变灯状态的操作
for (int i = 0; i <= 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx >= 0 && xx <= 4 && yy >= 0 && yy <= 4) g[xx][yy] ^= 1;
}
}

int main() {
int t;
scanf("%d", &t);
while (t--) {
int res = 0x3f3f3f;//因为后面res要和cnt取小,所以初始化无穷大
for (int i = 0; i < 5; i++)
scanf("%s", &g[i]);//字符串读入所给灯状态
for (int i = 0; i < 1 << 5; i++) {
//i<<5=32,因为一行灯有5个,所以第一行灯的所有改变情况一共有32次变化,枚举每一次变化后的第一行,从而去递推其后的每一行,取所有情况中最小的操作次数,即为最小操作次数
char bg[N][N];
int cnt = 0;//计算改变状态次数
memcpy(bg, g, sizeof g);//备份灯状态
for (int j = 0; j < 5; j++) {
if ((i >> j) & 1) {
//i当前位为1代表第一行这一位需要改变状态
turn(0, j);
++cnt;
}
}
for (int j = 0; j < 4; j++)
for (int k = 0; k < 5; k++)
if (g[j][k] == '0') {
//若当前灯关闭,则改变此位置下一行的状态
turn(j + 1, k);
++cnt;
}
bool f = true;//校验是否全部灯都为开启状态
for (int j = 0; j < 5; j++)
if (g[4][j] == '0') {
//直接看最后一行,若出现有一位关闭,则由当前首行的递推无解
f = false;
break;
}
res = f ? min(res, cnt) : res;
memcpy(g, bg, sizeof g);//换原初始的g
}
printf("%d\n", res <= 6 ? res : -1);
}
return 0;
}

费解的开关
http://example.com/2022/08/03/费解的开关/
作者
Charry
发布于
2022年8月3日
许可协议