洛谷P2040《打开所有的灯》

十月 02, 2018 3639

益(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;
}