洛谷P2040《打开所有的灯》

益(ruo)智(zhi)的小游戏

题目链接

题目背景

pmshz在玩一个益(ruo)智(zhi)的小游戏,目的是打开九盏灯所有的灯,这样的游戏难倒了pmshz。。。

题目描述

这个灯很奇(fan)怪(ren),点一下就会将这个灯和其周围四盏灯的开关状态全部改变。现在你的任务就是就是告诉pmshz要全部打开这些灯。

例如 0 1 1

1 0 0

1 0 1

点一下最中间的灯【2,2】就变成了

0 0 1

0 1 1

1 1 1

再点一下左上角的灯【1,1】就变成了

1 1 1

1 1 1

1 1 1

达成目标。最少需要2步。

输出2即可。

Input / Output 格式 & 样例

输入格式

九个数字,3*3的格式输入,每两个数字中间只有一个空格,表示灯初始的开关状态。(0表示关,1表示开)

输出格式

1个整数,表示最少打开所有灯所需要的步数。

输入样例

1
2
3
0  1  1
1 0 0
1 0 1

输出样例

1
2

解题思路

易证得我们对于一个灯的开关,只需要按1或0次

所以只需要考虑这个开关按与不按即可

所以我们可以直接进行搜索,总运算次数不会超过 9^9

used 数组记录 used_i 这个开关是否已经按过,用 f 数组记录 f_{i,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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
using namespace std;

namespace FastIO {
void DEBUG(char comment[], int x) {
cerr << comment << x << endl;
}

inline int getint() {
int s = 0, x = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') x = -1;
ch = getchar();
}
while (isdigit(ch)) {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * x;
}
inline void __basic_putint(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x >= 10) __basic_putint(x / 10);
putchar(x % 10 + '0');
}

inline void putint(int x, char external) {
__basic_putint(x);
putchar(external);
}
}

namespace Solution {
bool used[3 + 2][3 + 2];
int f[3 + 2][3 + 2], ans = 10;
const int dx[5] = {0, 0, 0, -1, 1};
const int dy[5] = {0, -1, 1, 0, 0};

void modify(int x, int y) {
for (int i = 0; i <= 4; ++i) {
f[x + dx[i]][y + dy[i]] = !f[x + dx[i]][y + dy[i]];
}
}

bool Check() {
for (int i = 1; i <= 3; ++i) {
for (int j = 1; j <= 3; ++j) {
if (!f[i][j]) return false;
}
}
return true;
}

void dfs(int steps) {
if (steps >= ans) return;
if (Check()) ans = std::min(ans, steps);
for (int i = 1; i <= 3; ++i) {
for (int j = 1; j <= 3; ++j) {
if (!used[i][j]) {
used[i][j] = true;
modify(i, j);
dfs(steps+1);
modify(i, j);
used[i][j] = false;
}
}
}
}
}

int main(int argc, char *const argv[]) {
#ifdef HANDWER_FILE
freopen("testdata.in", "r", stdin);
freopen("testdata.out", "w", stdout);
#endif
using namespace Solution;
for (int i = 1; i <= 3; ++i) {
for (int j = 1; j <= 3; ++j) {
f[i][j] = FastIO::getint();
}
}
dfs(0);
FastIO::putint(ans, '\n');
return 0;
}