Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

UVA1560 Extended Lights Out 解题报告

UVA1560 Extended Lights Out

有一个由按钮组成的矩阵,其中每行有6个按钮,共5行。每个按钮的位置上有一盏灯。当按下一个按钮后,该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。

即,如果灯原来是点亮的,就会被熄灭;如果灯原来是熄灭的,则会被点亮。在矩阵角上的按钮改变3盏灯的状态;在矩阵边上的按钮改变4盏灯的状态;其他的按钮改变5盏灯的状态。

请你写一个程序,确定需要按下哪些按钮,恰好使得所有的灯都熄灭。

根据上面的规则,我们知道

  1. 第2次按下同一个按钮时,将抵消第1次按下时所产生的结果。因此,每个按钮最多只需要按下一次

  2. 各个按钮被按下的顺序对最终的结果没有影响

  3. 对第1行中每盏点亮的灯,按下第2行对应的按钮,就可以熄灭第1行的全部灯。

如此重复下去,可以熄灭第1、2、3、4行的全部灯。同样,按下第1、2、3、4、5列的按钮,可以熄灭前5列的灯。

思路:

暴力模拟

这题的题面已经讲得很清楚了,我们分部分来考虑。

  1. 按下按钮

这里用了两个常量数组 dx,dy 来表示修改的五个位置。

因为每个位置只有 $0,1$ 两个状态,所以直接异或。

1
2
3
4
5
6
7
8
9
10
const int dx[5] = {0,0,1,0,-1},dy[5] = {0,1,0,-1,0};

void change(int x,int y) {
for (int i = 0;i < 5;++i) {
int ax = x + dx[i],ay = y + dy[i];
if (ax < 0 || ax > 4 || ay < 0 || ay > 5) continue;
a[ax][ay] ^= 1;
}
return ;
}
  1. 枚举点击方案

这里我们可以枚举第一行的点击方案,从第一行推出接下来的行如何点击。

这里用位运算可以很方便实现,我们把二进制意义的第 $i$ 位如果是 $1$ 则表示为按下,如果是 $0$ 则不动。

每次点击上一行为 1 的地方,保证操作完上一行全部都没点亮。

建议配合代码食用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i = 0;i < 6;++i) {
if (k & (1 << i)) {
change(0,i);
pos[0][i] = 1;
}
}//枚举第一行方案
for (int i = 1;i < 5;++i) {
for (int j = 0;j < 6;++j) {
if (a[i-1][j]) {
pos[i][j] = 1;
change(i,j);
}
}
}//根据第一行方案递推
  1. 检查方案是否合法

根据 2,我们可以直接检查最后一行是否全部是 0 ,如果是输出方案即可。

注意 UVA 对输出格式要求很严格 不能有多余的空格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool check() {
bool success = 1;
for (int i = 0;i < 6;++i) {
if (a[4][i]) {
success = 0;
}
}
return success;
}
if (check()) {
for (int i = 0;i < 5;++i) {
for (int j = 0;j < 5;++j) {
printf("%d ", pos[i][j]);
}
printf("%d\n",pos[i][5]);
}
return ;
}

下面给出全部代码

代码:

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
86
87
88
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <iostream>
using namespace std;
#define ll long long
#define ri register int

inline int read() {
char v = getchar();int x = 0,f = 1;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {x = x * 10 + v - 48;v = getchar();}
return x * f;
}
const int N = 10;
const int INF = 0x3f3f3f3f;

template <typename T> inline T max(T x,T y) {return x>y?x:y;}

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

void change(int x,int y) {
for (int i = 0;i < 5;++i) {
int ax = x + dx[i],ay = y + dy[i];
if (ax < 0 || ax > 4 || ay < 0 || ay > 5) continue;
a[ax][ay] ^= 1;
}
return ;
}

bool check() {
bool success = 1;
for (int i = 0;i < 6;++i) {
if (a[4][i]) {
success = 0;
}
}
return success;
}

void work() {
for (int k = 0;k < (1<<6);++k) {
int b[N][N],pos[N][N];
memset(pos,0,sizeof pos);
memcpy(b,a,sizeof(a));
for (int i = 0;i < 6;++i) {
if (k & (1 << i)) {
change(0,i);
pos[0][i] = 1;
}
}
for (int i = 1;i < 5;++i) {
for (int j = 0;j < 6;++j) {
if (a[i-1][j]) {
pos[i][j] = 1;
change(i,j);
}
}
}
if (check()) {
for (int i = 0;i < 5;++i) {
for (int j = 0;j < 5;++j) {
printf("%d ", pos[i][j]);
}
printf("%d\n",pos[i][5]);
}
return ;
}
memcpy(a,b,sizeof(b));
}
return ;
}

signed main() {
int T = read();
for(int q = 1;q <= T;++q) {
for (int i = 0;i < 5;++i) {
for (int j = 0;j < 6;++j) {
cin >> a[i][j];
}
}
printf("PUZZLE #%d\n",q);
work();
}
return 0;
}