ACW97
题意
你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态
1
2
3
4
5
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
1
2
3
4
5
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
1
2
3
4
5
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
输入格式
第一行输入正整数nn，代表数据中共有nn个待解决的游戏初始状态。
以下若干行数据分为nn组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
输出格式
一共输出nn行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。
数据范围
0<n≤5000<n≤500
输入样例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
输出样例：
1
2
3
3
2
-1
题意分析
发现此题数据量并不大(25个方格),但是求解却很复杂(搜索树的大小是2^25),但是中间有非常多的无效状态,可以将其剪枝,从而达到降低复杂度的效果
我们从这个角度思考一下:假设第一排的序列已经确定了,那么,我可以用第2排,将第一排全部清零(举个例子:a[1] = 0011,则翻转第二排的3,4位即可)(此时不在乎第二排的序列情况).然后第三排的也可以将第二排清零,根据数学归纳法,如此递推就能让除最后一排之外的所有排全部清零,而最后一排则无法被其他排清零,换句话说,第一行的初始状态直接决定最后一行的情况,当且仅当处理到最后一行时所有灯都被点亮,才算做一个合法状态,此题是在合法的状态下保证在六步(含)之内.
所以我们的目标就是枚举第一行的初始状态(共2^5种),然后搜索,每次搜索的复杂度是o(5*5),近似O(1)的复杂度,但是,枚举第一行的初始状态并不是直接枚举颜色组合(因为第一行的变化会牵扯到第二行),所以我们只能枚举第一行被翻转的状态,也就是一个五位二进制数,第j位为1表示第一排的第j位会被翻转(根据翻转的函数,其左右及下方也会翻转)
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <string>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int n;
int a[10][10];
int b[10][10];
void init() { // 输入
char ch;
for (int i = 1; i <= 5; ++i) {
for (int j = 1; j <= 5; ++j) {
cin >> ch;
a[i][j] = ch - '0';
}
}
}
void flip(int i, int j) { // 翻转位于(i,j)位置的方块
b[i][j] ^= 1;
b[i - 1][j] ^= 1;
b[i + 1][j] ^= 1;
b[i][j - 1] ^= 1;
b[i][j + 1] ^= 1;
}
bool check() { // 判断当前状态是否合法
for (int i = 1; i <= 5; ++i) {
for (int j = 1; j <= 5; ++j) {
if (!b[i][j]) {
return false;
}
}
}
return true;
}
int main() {
int T;
ios::sync_with_stdio(0);
cin >> T;
while (T--) {
init();
int ans = 0;
int minn = INF;
for (int i = 0; i < (1 << 6); ++i) { // 枚举第一位的翻转方式
ans = 0;
memcpy(b, a, sizeof(a)); // 每次仅操作b,a是副本
for (int j = 0; j < 6; ++j) { // 准确地说这里是枚举第一行所有翻转的可能
if ((i >> j) & 1) { // 考察其对应位0还是1
flip(1, 6 - j);
++ans;
}
}
for (int j = 2; j <= 5; ++j) {
for (int k = 1; k <= 5; ++k) {
if (!b[j - 1][k]) {
flip(j, k);
++ans;
}
}
}
if (check()) {
minn = min(ans, minn);
}
}
if (minn > 6) {
cout << -1 << endl;
} else {
cout << minn << endl;
}
}
return 0;
}
思考
其实这题的标签是位运算,实际上是一种简单的状态压缩问题,也就是对于一些布尔信息,可以考虑用位运算来解决,能节省空间以及加快速度
